프로그래머스 : 월간 코드 챌린지 시즌2 > 모두 0으로 만들기(lv3) c++

프로그래머스 링크

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

프로그래머스

문제 설명

각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다.

• 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한쪽은 1 감소시킵니다.

하지만, 모든 트리가 위의 행동을 통하여 모든 점들의 가중치를 0으로 만들 수 있는 것은 아닙니다. 당신은 주어진 트리에 대해서 해당 사항이 가능한지 판별하고, 만약 가능하다면 최소한의 행동을 통하여 모든 점들의 가중치를 0으로 만들고자 합니다.

트리의 각 점의 가중치를 의미하는 1차원 정수 배열 a와 트리의 간선 정보를 의미하는 edges가 매개변수로 주어집니다. 주어진 행동을 통해 트리의 모든 점들의 가중치를 0으로 만드는 것이 불가능하다면 -1을, 가능하다면 최소 몇 번만에 가능한지를 찾아 return 하도록 solution 함수를 완성해주세요. (만약 처음부터 트리의 모든 정점의 가중치가 0이라면, 0을 return 해야 합니다.)

---

제한사항

• a의 길이는 2 이상 300,000 이하입니다.
  • a의 모든 수는 각각 -1,000,000 이상 1,000,000 이하입니다.
  • a[i]는 i번 정점의 가중치를 의미합니다.
• edges의 행의 개수는 (a의 길이 - 1)입니다.
  • edges의 각 행은 [u, v] 2개의 정수로 이루어져 있으며, 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미합니다.
  • edges가 나타내는 그래프는 항상 트리로 주어집니다.

---

입출력 예 | a | edges | result

[-5,0,2,1,2]	[[0,1],[3,4],[2,3],[0,3]]	9
[0,1,0]	[[0,1],[1,2]]	-1

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 트리의 모든 정점의 가중치를 0으로 만드는 과정을 나타낸 것입니다.

1. 2번 정점과 3번 정점을 선택하여 2번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
2. 3번 정점과 4번 정점을 선택하여 4번 정점은 1 감소시키고, 3번 정점은 1 증가시킵니다. (2번 반복)
3. 0번 정점과 3번 정점을 선택하여 3번 정점은 1 감소시키고, 0번 정점은 1 증가시킵니다. (5번 반복)

• 모든 정점의 가중치를 0으로 만드는 데 필요한 최소 행동 횟수는 9번이므로, 9를 return 해야 합니다.

입출력 예 #2

• 주어진 트리는 모든 정점의 가중치를 0으로 만드는 것이 불가능하므로, -1을 return 해야 합니다.

코드 풀이

이번문제는 DFS탐색을 하여 리프노드까지 들어간 뒤 리프 노드에서부터 빠져나오면서 가중치값을 부모에 더해주어 처리해주는 방식으로 풀었습니다.

Q. 문제에서 트리의 가중치를 전부 0으로 만들어야 되는데 왜 이미지 Tree의 가중치는 전부 0이 아닌가요?

A. 리프에서부터 가중치를 부모에 더해서 최종적으로 루트노드의 가중치값이 0이라면 해당 트리의 가중치값은 전부 0이 가능한 트리입니다.
즉, 최종적으로 판단하는 방식은 루트노드의 0이냐 아니냐이기 때문에 따로 Cur노드의 가중치값을 빼주지 않았습니다.

기본적으로 아래와 같이 트리가 구성되어있다면 리프노드까지 탐색을 한다.

answer = 0

리프노드 까지 왔다면 해당 노드의 가중치값을 부모 노드에 더해준다.

이때 주의해야할 부분은 리프노드를 타고 들어갈 때 부모노드를 알 수 있게 코드를 짜야 된다.

answer = 0

마찬가지로 리프노드까지 타고 들어간 뒤 리프노드의 가중치값을 부모노드에 더한다

answer = 2

다부모노드로 돌아가 다시 자식 노드가 있다면 해당 노드로 탐색을 진행하여 리프노드까지 탐색 후 가중치 부모에 더함

answer = 4

마지막으로 루트노드에 3번 노드의 총 가중치값을 더해주어 최종 answer값을 도출한다

이때 0번 노드의 최종 가중치가 0이라면 answer을 출력하고 0이 아니라면 -1을 출력하면 된다.

answer = 9

코드

#include <string>
#include <vector>

using namespace std;

void DFS(const vector<vector<int>>& Graph, vector<long long>& Sum, 
         int Cur, int Parent, long long& answer)
{
    for(int i = 0; i < Graph[Cur].size(); ++i)
    {
        // 리프노드까지 이동
        if(Graph[Cur][i] != Parent)
        {
            DFS(Graph, Sum, Graph[Cur][i], Cur, answer);
        }
    }
    
    // 부모 노드에 현재 노드의 가중치값을 더해준다
    Sum[Parent] += Sum[Cur];
    // 정답을 도출하기위함
    answer += abs(Sum[Cur]);
}

long long solution(vector<int> a, vector<vector<int>> edges) {
    
    long long answer = 0;
    
    int aLength = a.size();
    
    // 자식 노드의 값을 부모노드에 계속해서 더하다보면
    // int 범위를 벗어날 수 있어 long long 타입의 벡터 선언
    vector<long long> Sum(aLength);
    
    for(int i = 0; i < aLength; ++i)
    {
        Sum[i] = a[i];
    }    
    
    // 그래프 선언
    vector<vector<int>> Graph(aLength);
    
    int EdgesSize = static_cast<int>(edges.size());
    
    for(int i = 0; i < EdgesSize; ++i)
    {
        // 그래프 연결
        Graph[edges[i][0]].push_back(edges[i][1]);
        Graph[edges[i][1]].push_back(edges[i][0]);
    }
    
    // DFS 탐색
    DFS(Graph, Sum, 0, 0, answer);
    
    if(Sum[0] != 0)
        return -1;
    
    return answer;
}