4534. 트리 흑백 색칠

4534. 트리 흑백 색칠

모든 경우를 탐색하는 것은 시간이 너무 오래 걸린다, 하지만 생각해보면 트리 순회처럼 재귀적으로 문제를 해결 할 수 있어 보였다.

그리고 최적 부분 구조라는 판단이 섰기 때문에, DP를 이용하여 문제를 풀어나갔다.

점화식은 'D[node][color] 로 node 에서 color 를 가질 때, 가질 수 있는 최대의 색칠 방법의 수' 라고 정의하였다.

이러한 점화식에 입각해서 생각해본다면, 

D[node][흰색] = D[next][검은색] + D[next][흰색]

D[node][검은색]=D[next][흰색]

이 된다.

###문제를 겪으면서 빠졌던 문제점###

처음에 계속 문제에서 빠뜨렸던 부분은, 한 노드에서 자식 노드가 2개 이상일 때에는, 자식 노드들의 최대 색칠 방법의 수를 전부다 곱해야 그 

노드의 최대 방법의 수가 나온다는 점이었다. 그래서 이 부분은 tmp 와 sum 함수를 for문에서 이용해서 해결할 수 있었다.

그리고 또 겪었던 문제점은 처음에 부모노드를 제외하고 연결된 노드가 있는지를 확인하는 과정에서 맨 처음에 visited[MAX] 배열을 선언해

서 방문체크 여부를 확인했었는데, 그럴경우에는 어떤 노드를 흰색에서 방문할 경우, 검정색에서 방문하지 못하는 문제점이 생겼다. 그래서 

이 부분은 그냥 재귀함수에서 parent 를 추가해줘서 메모리도 절약하면서 해결할 수 있었다.  

그리고 이런 문제에서 자주 실수하는 점은 변수의 범위이다. MOD 로 나누기 때문에 int 형 변수의 범위에서 해결할 수 있다는 착각을 하지만, 

계산과정에서 int 형 변수를 넘어가면 값의 오버플로우로 이상한 값이 저장되거나 그렇기 때문에 계산에 사용되는 변수는 모두 long long 으

로 바꾸어서 문제를 해결해야 했다. 또한 실수를 줄이기 위해 모든 계산에서 %MOD 연산을 적용시켰다.

<정답 코드>

#include<iostream>
#include<vector>
#define MAX 100001
#define MOD 1000000007
using namespace std;
 
int N;
long long ans;
long long D[100001][2];
int go(int parent,int node, int color,vector<vector<int>> &v)
{
    // 부모노드를 제외하고 연결된 노드가 있는지 확인, 즉 리프노드 여부를 판단
    int cnt = 0;
    for (int i = 0; i < v[node].size(); i++)
    {
        int next = v[node][i];
        if (next==parent)
            continue;
 
        cnt++;
    }
 
    // cnt==0 이면 리프노드
    if (cnt == 0)
        return 1;
 
    // 이미 값이 존재하는 경우 return 
    if (D[node][color] != -1)
        return D[node][color] % MOD;
 
 
    D[node][color] = 0;
 
    // 검정색일때
    if (color == 0)
    {
        long long tmp = 1;
        for (int i = 0; i < v[node].size(); i++)
        {
            long long sum = 0;
            int next = v[node][i];
            // 연결된 노드가 부모노드가 아닐 때
            if (next!=parent)
            {
                // 다음 노드에서의 최대값의 합을 구함
                sum += (go(node,next, 1, v)) % MOD;
                sum %= MOD;
 
                // node에 연결된 여러개의 next 의 합의 곱을 이용하여 총 갯수를 구함.
                tmp *= sum;
                tmp %= MOD;
            }
        }
        // 구한 값을 저장
        D[node][color] = tmp;
    }
    
 
    // 흰색일때
    if(color==1)
    {
        long long tmp = 1;
        for (int i = 0; i < v[node].size(); i++)
        {
            long long sum = 0;
            int next = v[node][i];
 
            // 연결된 노드가 부모노드가 아닐 때
            if (next!=parent)
            {
                // 다음 노드에서의 최대값의 합을 구함
                sum += ((go(node,next, 0, v)) % MOD) + ((go(node,next, 1, v)) % MOD);
                sum %= MOD;
 
                // node에 연결된 여러개의 next 의 합의 곱을 이용하여 총 갯수를 구함.
                tmp *= sum;
                tmp %= MOD;
            }
 
        }
 
        // 구한 값을 저장
        D[node][color] = tmp;
    }
 
    return D[node][color];
 
 
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        for (int i = 0; i < MAX; i++) {
            D[i][0] = -1;
            D[i][1] = -1;
        }
 
        cin >> N;
        vector<vector<int>> v(N+1);
 
        // 간선 연결
        for (int i = 1; i < N; i++)
        {
            int from, to;
            cin >> from >> to;
            v[from].push_back(to);
            v[to].push_back(from);
        }
 
        ans = (go(-1,1, 0, v)%MOD + go(-1,1, 1, v)%MOD)%MOD;
 
        cout <<"#"<<t<<" "<< ans << endl;
 
    }
 
    return 0;
}