Programmers 76503 모두 0으로 만들기

17 Apr 2021 in Algorithm

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/76503

나의 풀이

먼저 모든 점들의 가중치를 0으로 불가능한 경우는 모든 가중치들의 합이 0이 아닌경우이다. 반대로 모든 가중치들의 합이 0이라면 모든 점들의 가중치를 0으로 만드는 것이 가능하다.

임의의 정점으로 dfs를 수행하여 가장 끝에있는 노드부터 가중치를 0으로 값을 조정한다.
노드의 가중치를 0으로 만들기 위해서는 가중치 a만큼 뺴야하기 때문에 자식 노드의 가중치는 a를 뺴고 부모 노드의 가중치에는 a를 더한다. 이 때 |a|번 연산을 하는 것이기 때문에 최종 정답에 |a| 만큼 더해준다.

풀이 코드 : 76503 모두 0으로 만들기

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> map;
vector<int> visit;
long long dfs(int idx, int pre_idx, vector<long long> &a){
    long long res = 0;
    visit[idx] = 1;
    for(int i=0;i<map[idx].size();i++){
        int next = map[idx][i];
        if(visit[next] == 0){
            res += dfs(next, idx, a);
        }
    }  
    long long num = a[idx];
    a[pre_idx] += num;
    a[idx] = 0;
    if(num >= 0) res += num;
    else res += -num;
    
    return res;
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    long long answer = 0;
    long long sum = 0;
    vector<long long> new_a;
    for(int i=0;i<a.size();i++){
        sum += a[i];
        new_a.push_back(a[i]);
    }
    if(sum != 0) return -1;
    int size = a.size();
    visit.resize(size);
    map.resize(size);
    for(int i=0;i<edges.size();i++){
        map[edges[i][0]].push_back(edges[i][1]);
        map[edges[i][1]].push_back(edges[i][0]);
    }
    answer = dfs(0, 0, new_a);
    return answer;
}

채점결과