[ SWEA 4534 ] 트리 흑백 색칠 (C++)

SWExpertAcademy의 트리 흑백색칠(4534 / D5) 문제이다.

[ 문제풀이 ]

본인은 이 문제를 완전탐색, 그 중에서도 깊이 우선 탐색(DFS) 기법을 이용해서 접근하였다.

그런데 ! 단순히 완전탐색을 이용해서 문제를 풀게 된다면 주어지는 노드의 갯수가 최대 10만개 이기 때문에

시간초과가 발생하게 된다.

따라서 DFS + 메모이제이션을 이용해서 접근하였다.

가장 먼저, 가장 첫 노드는 어떤 노드로 설정해 주어도 상관이 없다.

본인은 무난하게 1번노드를 첫 번째 노드로 설정하고 탐색을 시작해주었다.

첫 번째 노드는 하얀색이든 검은색이든 뭘로 색칠을 해도 상관이 없다.

따라서, 하얀색으로 칠하면서 탐색을 시작하는 경우와, 검은색으로 칠하면서 탐색을 칠하는 경우 2가지 경우를 모두 다

탐색한 후에, 각각의 결과값을 더해주어야 한다.

( 하얀색으로 시작했을 때 발생할 수 있는 경우의 수 + 검은색으로 시작했을 때 발생할 수 있는 경우의 수 = 모든 경우의 수 )

본격적인 탐색을 할 때에는, 현재 노드가 하얀색이라면, 그 다음 노드를 하얀색으로 칠하는 경우와 검은색으로 칠하는 경우를 각각 계산한 후에 더해주었다.

현재 노드가 검은색이라면, 반드시 그 다음 노드를 하얀색으로 칠하는 경우만 탐색을 해 주었다.

정리해서 이야기해보면, 현재 노드가 x번 노드이고, 그 다음 칠해야 할 노드 nx번 노드라고 한다면,

x번 노드를 하얀색으로 칠했을 때, 트리를 칠할 수 있는 경우의 수 =

nx번 노드를 하얀색으로 칠했을 때 발생할 수 있는 경우의 수 + nx번 노드를 검은색으로 칠했을 때 발생할 수 있는 경우의 수

x번 노드를 검은색으로 칠했을 때, 트리를 칠할 수 있는 경우의 수 = nx번 노드를 하얀색으로 칠했을 때 트리를 칠할 수 있는 겨우의 수 가 된다는 것이다.

이를 코드로 표현하기 위해서 DP[][]라는 2차원 배열을 하나 사용해 주었는데,

DP[A][B] = C 의 의미는, "A번 노드를 B색깔로 칠했을 때, 전체 트리를 칠할 수 있는 경우의 수는 총 C개입니다." 를 의미한다.

따라서, 배열에서 'B'가 들어가는 부분의 크기는 2칸만 설정해 주었다. 왜냐하면, 칠할 수 있는 색이 하얀색, 검은색 2가지 밖에 없기 때문이다.

또한, 메모이제이션을 이용하기 위해서, "아직 탐색하지 않은 상황을 -1로 미리 설정" 해주었다.

만약, -1이 아닌 0으로 그대로 둔다면, DP[A][B] = 0 이라는 결과값이 있다면, A번 노드를 B색깔로 칠했을 떄, 전체 트리를 칠할 수 있는 경우의 수가 없다라는 것을 의미하는지, 아니면 계산된적이 없다는 건지 구분할 수 없기 때문이다.

따라서, -1로 초기값을 세팅해 주었고, DP[A][B]의 값이 -1이라면, 탐색을 한 적이 없었으므로 탐색을 진행해주면 되고,

만약 -1이 아니라면, 이미 탐색해본 적이 있는 상황이니, 그대로 DP[A][B]의 값을 return 하는 방식으로 진행해 주었다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
#include <vector>
 
#define endl "\n"
#define MAX 100010
#define MODULER 1000000007
using namespace std;
 
int N;
long long Answer;
long long DP[MAX][2];
vector<int> Node[MAX];
 
void Initialize()
{
    for (int i = 0; i < MAX; i++) Node[i].clear();
    memset(DP, -1, sizeof(DP));
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N - 1; i++)
    {
        int a, b; cin >> a >> b;
        Node[a].push_back(b);
        Node[b].push_back(a);
    }
}
 
long long DFS(int Cur, int Color, int Parent)
{
    if (DP[Cur][Color] != -1) return DP[Cur][Color];
    DP[Cur][Color] = 1;
    
    for (int i = 0; i < Node[Cur].size(); i++)
    {
        int Next = Node[Cur][i];
        if (Next == Parent) continue;
        
        if (Color == 0)
        {
            DP[Cur][Color] = DP[Cur][Color] * (DFS(Next, 0, Cur) + DFS(Next, 1, Cur));
            DP[Cur][Color] = DP[Cur][Color] % MODULER;
        }
        else
        {
            DP[Cur][Color] = DP[Cur][Color] * (DFS(Next, 0, Cur));
            DP[Cur][Color] = DP[Cur][Color] % MODULER;
        }
    }
    return DP[Cur][Color];
}
 
void Solution()
{
    long long Result = DFS(1, 0, -1) % MODULER;
    long long Result2 = DFS(1, 1, -1) % MODULER;
    Answer = Result + Result2;
    Answer = Answer % MODULER;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}