[Algorithm] Programmers :: 모두 0으로 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/76503

프로그래머스

vector<vector<int>> graph(300001);
vector<int> weights;
long long answerCount = 0;
 
long long DFS(int parentNode, int curNode)
{
    long long curWeight = weights[curNode];
 
    for (int i = 0; i < graph[curNode].size(); ++i)
    {
        int node = graph[curNode][i];
 
        if (node == parentNode) continue;
 
        curWeight += DFS(curNode, node);
    }
 
    answerCount += abs(curWeight);
    return curWeight;
}
 
long long solution(vector<int> a, vector<vector<int>> edges) 
{
    long long answer = 0;
    weights = a;
    
    long long rootWeight = a[0];
 
    for (int i = 0; i < edges.size(); ++i)
    {
        int first = edges[i][0];
        int second = edges[i][1];
 
        graph[first].push_back(second);
        graph[second].push_back(first);
    }
 
    for (int i = 0; i < graph[0].size(); ++i)
    {
        int node = graph[0][i];
 
        answer += DFS(0, node);
    }
 
    if (answer + rootWeight != 0) return -1;
 
    return answerCount;
}

모든 노드의 가중치를 0으로 만들기 위한 최소횟수를 구하는 문제이다.

 

양방향이기 때문에 아무노드나 루트노드로 삼고, 리프노드(자식이 없는 노드, 즉 맨 끝노드) 까지 깊이탐색한다음에 거기서부터 값을 0으로 만들면서 그만큼의 변경된값을 부모한테 넘기는식으로 진행하면 된다.

최종적으로 루트노드로 값이 다 모이게 될 것이고 해당 루트노드값이 0이어야만 문제의 조건을 충족하게 된다.

0이 아니라면 -1을 리턴해주면 된다.

 

노드는 최대 30만개이고 값은 -1000,000 ~ 1000,000 이기 때문에 반드시 long long으로 해줘야 한다.

그리고 루트노드가 자식노드들한테 값을 다 넘겨받은 다음, 자기자신의 가중치값도 더해주는것도 잊으면 안된다.