[프로그래머스/C++] 모두 0으로 만들기

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 트리를 따라서 트리에 저장되어 있는 수들을 0으로 만드는 문제다.

 

이때 서로 연결된 노드를 기준으로 한쪽 노드는 +1, 한쪽 노드는 -1을 수행할 수 있다.

 

이를 요약하면 a노드에서 b노드로 숫자를 옮긴다고 볼 수 있다.

 

a노드에 5가 저장되어 있고, b노드에 3이 저장되어 있다면, a노드의 5를 b노드에 더하고 a노드를 0으로 만들 수 있다.

(이 때 연산의 횟수는 a노드에 저장된 수의 절댓값인 5 이다.)

 

여기서 모든 노드를 0으로 만들때 필요한 연산의 횟수를 return하라고 했는데, 이를 계산하기 위해서는 특정 노드를 기준으로 DFS 탐색을 하면서 계산하면 된다.

 

예를 들어 0번 노드를 기준으로 아래와 같은 트리가 있다. 

0번 노드를 기준으로 DFS 탐색을 시작하면, 다음과 같은 과정을 거치게 될 것이다.

위와 같은 과정을 거쳐서 모든 트리는 0이 되게 된다. 

 

즉, 특정 노드를 최상단 노드로 하는 트리를 만들고, leaf노드부터 부모노드로 자신의 숫자를 이동하는 연산을 반복하면 모든 노드를 0으로 만드는데 걸리는 최소연산 횟수를 구할 수 있다.

 

이 방법이 가능한 이유는 왜 일까?

위 그림을 보면 같은 부호의 숫자들이 공통조상에서 만나서 합쳐지는 것과, 따로 특정 노드까지 이동하는 것은 횟수가 같다.

 

만약 부호가 다르다면 공통 조상에서 합쳐져서 연산의 수가 줄어들게 된다.

그렇기 때문에 DFS로 공통조상에서 자식들의 수들을 합친 다음에, 이동하는 것이 항상 최솟값이다.

 

+ 모든 노드를 0으로 만들 수 있기 때문에 이렇게 아무 노드를 특정 노드로 잡아도 연산의 최솟값이 되는 것이다.

 

 

 

[아이디어 정리]

1. 특정 노드를 최상위 노드로 하는 트리를 그리고, 자식 노드들을 재귀로 탐색한다.
2. 자식 노드들은 자신에게 저장된 값을 부모노드에 더하고 지금까지 몇 번 연산 했는지 return한다.
3. 최상단 노드가 0인지 확인하고, 0이라면 연산 횟수를 return하고 0이 아니라면 -1을 return 한다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long search(int nowN, int parN, vector<vector<int>> &nlst,vector<long long> &a)
{
    long long retAns=0;
    for (int i=0; i<nlst[nowN].size(); i++)
    {
        if (nlst[nowN][i]!=parN)
        {
            retAns+=search(nlst[nowN][i], nowN, nlst,a);
        }
    }
    retAns+=abs(a[nowN]);
    a[parN]+=a[nowN];
    if (parN!=nowN)
    {
        a[nowN]=0;
    }
    return retAns;
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    vector<long long> aa(a.begin(), a.end());
    vector<vector<int>> nlst(a.size());
    for (int i=0; i<edges.size(); i++)
    {
        nlst[edges[i][0]].push_back(edges[i][1]);
        nlst[edges[i][1]].push_back(edges[i][0]);        
    }
    long long ans=search(0,0,nlst,aa);
    if (aa[0]==0)
        return ans;
    return -1;
}

 

---

 

중간에 분명 풀이가 맞는것 같은데 틀렷다고 나왔다...

혹시 해서 제한사항을 봤더니 int 값의 범위를 넘어갈 수 있었기 때문에 변수의 type을 long long으로 바꿔서 해결했다

하마터면 변수 타입 때문에 고생할 뻔

프로그래머스