프로그래머스 문제 - 모두 0으로 만들기

프로그래머스 모두 0으로 만들기 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

각 점에 가중치가 부여된 트리가 주어집니다.
임의의 연결된 두 점을 골라서 한쪽은 1을 증가시키고 한쪽은 1을 감소시키는 연산을 통해 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.
모든 점들의 가중치를 0으로 만들 때 최소 몇 번 안에 가능한지 찾아야합니다. 만약 0으로 만들지 못할 경우 -1을 리턴해야 합니다.

문제 풀이

주어진 가중치들을 더하고 빼주며 0을 만드는데 최소한의 횟수를 찾는 문제입니다.
처음 문제를 볼땐 정말 이해가 되지 않았지만 주어진 예제와 그림들을 보며 해결법을 찾아내었습니다.

트리 구조로 되어있기 때문에 어디서든 부모 노드로 시작해도 연결된 모든 노드에 접근할 수 있으므로 원하는 노드를 부모 노드로 잡고 모든 노드를 거치며 가중치를 확인하면 됩니다.
0번 노드가 부모 노드로 하는 것이 좋아서 0번을 부모 노드로 맞춘 후 계산하였습니다.

예제들을 확인해보면 0이 될 수 있는 트리는 주어진 가중치들을 전부 더하면 0이라는 값이 나오게 됩니다.
그러니 모두 더하여 0이 나오지 않는다면 주어진 트리는 불가능한 트리로 판단하여 -1을 리턴하면 됩니다.

하지만 0이 나온다면 모든 노드를 돌아다니며 연산된 수를 저장해주면 됩니다.
부모 노드와 자식 노드들의 관계를 보면 자식 노드들도 가중치가 0이 되어야 하기 때문에 자신의 가중치 값을 0으로 만드는 연산을 실행하게 됩니다.
그러므로 DFS를 통해 아래서부터 자식들을 0으로 만들어나가며 계산하게 되면 최소 횟수를 알아낼 수 있습니다.
즉 자식들의 가중치를 부모 노드의 가중치에 더해준 후 자식들의 가중치의 절대값을 전부 더해주게 되면 모든 가중치를 0으로 만드는 최소 횟수가 나오게 됩니다.

전체 코드

문제를 해결하다 함수에 커다란 배열을 넣게 될 경우 시간초과의 원인이 될 수 있다는 것을 알게 되었습니다.
양방향 간선이 역으로 찾지 않기 위해서는 자식 노드를 참조할 때 부모 노드를 알려주어 참조하지 않도록 하면 됩니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

vector<long long> indexNum;
vector<int> node[300000];
long long sum;

long long solve(int cur, int parent)
{
    
    long long curSum = indexNum[cur];
    for(int n : node[cur])
    {
        if(n != parent)
        {
            //자식 노드들의 가중치를 찾아 더해줌
            curSum += solve(n, cur);
        }
    }
    //현재까지 진행된 가중치를 전부 더해줌
    sum += abs(curSum);
    return curSum;
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    long long answer = -2;
    
    //각 인덱스의 값들 저장
    for(int i = 0; i < a.size(); i++)
    {
        indexNum.push_back(a[i]);
    }
    
    sum = 0;
    for(int n : a)
    {
        sum += n;
    }
    //만약 모든 가중치를 더했을 때 0이 나오지 않으면 0 만드는 것이 불가능한 트리
    if(sum != 0)
    {
        answer = -1;
    }
    else
    {
        //각 간선들을 트리로 만들어줌
        for(vector<int> v : edges)
        {
            node[v[0]].push_back(v[1]);
            node[v[1]].push_back(v[0]);
        }
        
        solve(0, 0);
        
        answer = sum;
    }
    
    return answer;
}

출저

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