[ 프로그래머스 [ 월간코드챌린지 ] 모두 0으로 만들기 ] (C++)

프로그래머스의 모두 0으로 만들기(월간코드챌린지) 문제이다.

 

[ 문제풀이 ]

주어진 트리의 모든 노드들의 가중치를 0으로 만들 때, 최소 몇 번 만에 가능한지를 구해야 하는 문제이다.

문제를 해결하기 위해서 필요한 정보들에 대한 이야기부터, 정답을 도출하는 과정까지 단계별로 진행해보자.

 

#1. "반드시" 0으로 만들지 못하는 경우

우리는 주어진 트리에 존재하는 모든 노드들의 가중치를 0으로 만들어야 한다.

만약, 그럴 수 없다면 -1을 return 시켜주어야 한다.

그렇다면 어느 경우에 모든 노드들의 가중치를 0으로 만들 수 있는지 없는지에 대해서 부터 파악해보자.

먼저, 우리는 가중치를 0으로 만들기 위해서 "하나의 간선으로 연결된 2개의 정점을 골라서, 한 쪽은 1을 증가시키고, 다른 한쪽은 1을 감소시키는 과정"을 진행할 것이다.

즉 ! 어느 한 정점의 가중치가 증가한다면, 다른 한 정점의 가중치가 감소하게 된다는 것이다.

어떤 노드는 가중치가 음수라서 0으로 만들기 위해서 증가 시켜야 할 것이고, 어떤 노드는 가중치가 양수라서 0으로 만들기 위해서 감소 시켜야 할 것이다. 우리는 이러한 과정 속에서 모든 노드들의 가중치를 0으로 만들어 주어야 한다.

그렇다면 어떤 경우에만 모든 정점들의 가중치를 0으로 만들 수 있을까 ?? 바로 "모든 정점들의 가중치의 합이 0이되는 경우" 에만 가능하다는 것이다. 보다 구체적으로 이야기해보면, "모든 정점들이 0으로 되는 과정속에서, 증가되는 양과 감소하는 양이 동일한 경우에만 모든 정점들의 가중치를 0으로 만들 수 있다" 라는 것이다.

따라서 우리는 주어진 입력 중, 정점들의 가중치 리스트를 통해서 그 합을 구한 후, 0이 아니라면 탐색을 해볼 필요도 없이 이 경우에는 "반드시 0으로 만들지 못하는 경우" 라는 것을 알 수 있다.

# 어느 하나의 정점이 증가하면, 다른 하나의 정점은 감소하기 때문에, 증가하는 양과 감소하는 양이 동일해야만 한다.
# 모든 정점들의 가중치의 합이 0인 경우에만 모든 노드들의 가중치를 0으로 만들 수 있다.
# 그렇지 않은 경우, 탐색을 해볼 필요도 없이 반드시 0으로 만들지 못하므로 "-1을 return" 시키면 된다.

 

#2. 가중치 복사하기

이 과정은 사실 우리가 진행하는 단계 중, 현재 단계에서 반드시 해야하는 과정은 아니지만, 후에 사용할 것을 대비해서 미리 진행하는 과정이다. 바로 가중치에 대한 정보를 복사하는 과정이다.

문제에서 우리에게 2가지 정보를 준다. 그 중 하나가 "노드들이 가지고 있는 가중치를 저장하고 있는 리스트" 이다.

우리는 이 리스트를 통해서 #1의 과정(모든 가중치의 합이 0이 되는지 안되는지 판단)을 진행하기도 하였다.

그런데 본인은 #1의 과정을 진행함과 동시에, 이 리스트를 본인이 선언한 새로운 리스트에 복사를 해 주었다.

왜 복사를 해주어야 할까 ?? 그냥 주어진 정보를 그대로 사용하면 무엇이 문제가 될까 ?? 이를 알아보기 위해서 먼저 주어진 정보에 대해서 분석을 해보자.

1. 각 노드들의 가중치가 들어있는 리스트는 'int'형으로 주어진다.

2. 모든 가중치는 -1,000,000 ~ 1,000,000 이다.

3. 리스트의 길이는 2 ~ 300,000 이므로, 주어지는 정점의 갯수는 2개 ~ 300,000개 라는 것을 의미한다.

그런데 ! 우리는 지금부터 모든 정점들의 가중치를 0으로 만들기 위해서 어떤 노드의 가중치는 더할 것이고, 어떤 노드의 가중치는 감소 시킬 것이다. 그렇게 된다면, 우리에게 주어진 기존의 리스트에 저장되어 있는 가중치들이 증가되기도 하고 감소되기도 하면서 그 수치가 바뀌게 될 것이다. 여기서 "정점들이 가지고 있는 가중치가 바뀌게 되는 것"이 문제이다.

최악의 경우 가중치가 1,000,000 이고 정점이 300,000개가 주어진다면, 이를 계산하는 과정에서 int형의 범위를 벗어나는 문제가 발생하게 된다. 따라서, 본인은 이 가중치가 들어있는 리스트를 본인이 선언한 long long크기의 새로운 리스트에 다시 복사해서 저장해 주었다.

# 주어진 가중치의 리스트를 그대로 사용하게 될 경우, 이후에 있을 가중치를 증감시키는 과정에서 int형의 범위를
   벗어날 수 있다.
# 이를 위해서, long long형의 크기를 가진 새로운 리스트에 주어진 리스트를 복사한다.

다음은 #1의 과정과 #2의 과정을 코드로 구현한 내용이다.

long long Copy_And_Calculate_Sum(vector<int> &A, vector<long long> &Weight)
{
	long long Sum = 0;
	for (int i = 0; i < A.size(); i++)
	{
		Sum += A[i];
		Weight[i] = (long long)(A[i]);
	}
	return Sum;
}

 

#3. Tree 만들기

이제 본격적으로 문제를 해결하기 위해서 본인은 가장 먼저 Tree를 만들어 주었다.

주어진 간선 정보들을 통해서 노드와 노드간의 연결관계를 만들어 주었고, 이를 2차원 Vector에 저장해 주었다.

이 과정은 간단하지만, #4에서 진행될 더 중요한 과정까지 모두 알아본 후에 코드로 확인해보자.

 

#4. Leaf Node 찾기

제목만 보면, 리프노드를 찾는 과정이다. 먼저, 리프노드가 어떤 노드인지에 대해서부터 간략하게 알아보자.

리프노드(LeafNode)라는 것은, 트리에서 자식을 가지고 있지 않은, 보다 전문적이지 않은 말로 표현하면 그림으로 봤을 때 가장 말단에 위치하는 노드를 리프노드라고 한다.

그런데 ! 갑자기 이 리프노드들을 왜 찾아야 할까 ?? 리프노드들은 연결된 정점이 자식이 없으므로, 해당 노드들의 부모 노드랑만 연결이 되어 있을 것이다. 그리고 그 부모 노드는 또 다른 부모 노드가 있을 것이고, 타고 타고 올라가면 루트노드 까지 연결이 되어 있을 것이다. 그럼 ! 여기서 루트노드부터 가중치를 0으로 만드는 과정을 진행했다고 생각을 해보자.

정말 스무스하게 진행이 잘 되어서, 리프노드의 부모노드까지 가중치를 0으로 만드는데 성공했고 이제 0으로 만들 노드는 리프노드만 남았다고 생각을 해보자.  이 리프노드를 0으로 만들기 위해 해당 가중치만큼 증가시키거나 감소시키는 순간, 해당 리프노드의 부모노드는 이미 0임에도 불구하고, 다시 가중치가 바뀌게 될 것이다. 그럼 다시 이 부모노드를 0으로 만들기 위한 여러가지 다른 과정을 또 진행하게 된다면, 결국 모든 정점을 0으로 만들 수 있는 경우가 발생 할 수 는 있지만, 그 과정의 횟수를 따져 봤을 때, 그 횟수는 문제에서 요구하는 "0으로 만들기 위한 연산의 최소 횟수" 라는 보장이 없다는 것이다.

따라서, 최소 연산의 횟수만으로 모든 정점을 0으로 만들기 위해서는 리프노드부터 0으로 만들어 주어야 한다.

그럼 ! 이 문제에서 리프노드를 어떻게 구할 수 있을까 ??

본인은 정말 간단하게 "연결되어 있는 간선의 수가 1개인 정점" 을 리프노드로 판단해 주었다.

리프노드라면, 연결되어 있는 간선이 자기 부모와 연결되어 있는 간선 1개뿐일 것이기 때문이다.

그래서 이 리프노드들부터 탐색을 시작하기 위해서 리프노드들만 따로 저장을 해 주었다.

#3의 과정과 #4의 과정을 코드로 구현하면 다음과 같다.

void Make_Tree(vector<vector<int>> Edges, vector<int> &LeafNode, vector<int> &EdgeCnt, vector<vector<int>>& Tree, int NodeCnt)
{
	for (int i = 0; i < Edges.size(); i++)
	{
		int N1 = Edges[i][0];
		int N2 = Edges[i][1];
		Tree[N1].push_back(N2);
		Tree[N2].push_back(N1);
		EdgeCnt[N1]++;
		EdgeCnt[N2]++;
	}
	for (int i = 0; i < NodeCnt; i++)
	{
		if (EdgeCnt[i] == 1) LeafNode.push_back(i);
	}
}

 

#5. 모두 0으로 만들기

이제 정점들을 모두 0으로 만드는 과정을 진행해보자. 본인은 이 과정을 자료구조 Queue를 이용해서 구현해 주었다.

가장 초기에는 Queue에 #4의 과정에서 구해놓은 리프노드들을 넣어주고 탐색을 시작하였다.

노드들을 탐색하면서 해당 노드의 가중치를 0으로 만들어 주고, 0으로 만든 후에는 이 노드를 이미 0으로 만들어 버린 노드라고 표시를 해 주었다. 또한, 0으로 만들어 버리는 과정에서 연결되어 있는 또 다른 노드 입장에서는 "해당 노드와 연결되어 있는 노드 중 하나가 이미 0이 되었으므로 없는 노드 취급" 하기 위해서 #4의 과정에서 구해놓은 "연결되어 있는 간선의 갯수"를 감소시켜 주었다. 이런식으로 연결되어 있는 간선의 갯수를 감소시키는 과정에서 또 다른 리프노드(연결되어 있는 간선의 갯수가 1개인 정점)가 발생할 것이다. 이러한 정점이 발생한다면 계속해서 Queue를 삽입하면서 진행해 주었다.

 

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <cmath>
 
using namespace std;
 
long long Copy_And_Calculate_Sum(vector<int> &A, vector<long long> &Weight)
{
    long long Sum = 0;
    for (int i = 0; i < A.size(); i++)
    {
        Sum += A[i];
        Weight[i] = (long long)(A[i]);
    }
    return Sum;
}
 
void Make_Tree(vector<vector<int>> Edges, vector<int> &LeafNode, vector<int> &EdgeCnt, vector<vector<int>>& Tree, int NodeCnt)
{
    for (int i = 0; i < Edges.size(); i++)
    {
        int N1 = Edges[i][0];
        int N2 = Edges[i][1];
        Tree[N1].push_back(N2);
        Tree[N2].push_back(N1);
        EdgeCnt[N1]++;
        EdgeCnt[N2]++;
    }
    for (int i = 0; i < NodeCnt; i++)
    {
        if (EdgeCnt[i] == 1) LeafNode.push_back(i);
    }
}
 
void Func(long long &answer, vector<long long> Weight, vector<int> Leaf, vector<int> Edge_Cnt, vector<vector<int>> Tree, int Node_Cnt)
{
    vector<bool> Visit(Node_Cnt, false);
    queue<int> Q;
    for (int i = 0; i < Leaf.size(); i++) Q.push(Leaf[i]);
 
    while (Q.empty() == false)
    {
        int Cur = Q.front();
        long long Cur_Weight = Weight[Cur];
        Visit[Cur] = true;
        Q.pop();
 
        for (int i = 0; i < Tree[Cur].size(); i++)
        {
            int Next = Tree[Cur][i];
            if (Visit[Next] == true) continue;
 
            Weight[Cur] -= Cur_Weight;
            Weight[Next] += Cur_Weight;
            answer += abs(Cur_Weight);
            Edge_Cnt[Next]--;
            if (Edge_Cnt[Next] == 1) Q.push(Next);
        }
    }
}
 
long long solution(vector<int> a, vector<vector<int>> edges)
{
    long long answer = 0;
 
    vector<long long> Weight(a.size(), 0);
    long long Result = Copy_And_Calculate_Sum(a, Weight);
    if (Result != 0) return -1;
 
    vector<int> LeafNode;
    vector<int> Edge_Cnt(a.size(), 0);
    vector<vector<int>> Tree(a.size(), vector<int>());
    Make_Tree(edges, LeafNode, Edge_Cnt, Tree, a.size());
    Func(answer, Weight, LeafNode, Edge_Cnt, Tree, a.size());
    return answer;
}