BOJ 백준 19535번 ㄷㄷㄷㅈ

 

BOJ 백준 19535 ㄷㄷㄷㅈ

 

문제: https://www.acmicpc.net/problem/19535

19535번: ㄷㄷㄷㅈ

 

 

 

정점 수가 N인 트리가 주어졌을 때, 4개의 정점으로 이루어진 ㄷ’ 모양의 서브트리와 ‘ㅈ’ 모양의 서브트리 개수에 3배한 값을 비교하여 해당 트리가 어떤 트리에 속하는지 출력해야 한다. (4 ≤ N ≤ 300,000)

 

 

 

처음에 이 문제를 보고 (트리에서의) 다이나믹 프로그래밍(Dynamic Programming)으로 해결하는 문제일 것으로 예상했다. 그러나 실제로 확인해보니 굳이 거창하게 다이나믹 프로그래밍까지 확장하여 생각할 필요는 없었다. 임의의 서브 트리를 예로 들어서 ‘ㄷ’ 모양과 ‘ㅈ’ 모양의 서브 트리를 어떻게 셀 수 있는지 확인해 보자.

 

 

 

 

임의의 트리에서 노드 1부터 시작해서 노드 now까지 DFS(Depth-First Search)로 탐색했을 때, now를 root로 갖는 서브트리를 그려보았다. 그러면 현재 방문 중인 노드는 now이고, now의 자식 노드 중 임의의 한 노드를 next라고 가정한다. 그리고 각 노드의 깊이를 저장하는 depth 배열을 따로 설정한다.

 

현재 방문 중인 노드: now

now의 임의의 자식 노드: next

depth[i]: 노드 i의 깊이

 

이 때, 노드 now를 기준으로 만들어지는 ‘ㅈ’, ‘ㄷ’ 트리의 개수를 세어 보자.

 

 

 

노드 now를 포함하는 ‘ㅈ’ 트리는 크게 두 가지 경우로 나눌 수 있다. 하나는 노드 now가 ‘ㅈ’ 트리의 끄트머리에 달려 있는 경우(직접 연결된 노드가 1개일 때), 다른 경우는 노드 now가 ‘ㅈ’ 트리의 가운데에 위치하는 경우(직접 연결된 노드가 3개일 때)이다. 전자를 경우 A, 후자를 경우 B라고 하자.

 

 

경우 A를 만족하려면 next의 자식 노드 중 2개를 골라서 ‘ㅈ’ 트리를 형성해야 한다. 따라서 가능한 경우의 수는 next의 자식 노드에서 서로 다른 두 개의 노드를 선택하는 조합과 같다.

 

 

경우 B를 만족하려면 now의 자식 노드 중 3개를 골라서 ‘ㅈ’ 트리를 형성해야 한다. 따라서 가능한 경우의 수는 now의 자식 노드에서 서로 다른 세 개의 노드를 선택하는 조합과 같다.

 

 

 

마찬가지로 노드 now를 포함하는 ‘ㄷ’ 트리는 크게 두 가지 경우로 나눌 수 있다. 하나는 노드 now가 ‘ㄷ’ 트리의 끄트머리에 달려 있는 경우(직접 연결된 노드가 1개일 때), 다른 경우는 노드 now가 ‘ㄷ’ 트리의 가운데에 위치하는 경우(직접 연결된 노드가 2개일 때)이다. 전자를 경우 C, 후자를 경우 D라고 하자.

 

 

경우 C를 만족하려면 현재 노드 now에서 자식을 따라 3번의 간선을 걸쳐서 내려갔을 때도 노드가 존재하면 된다. 따라서 depth[now] + 3과 같은 깊이를 가진 노드의 개수를 구한다.

 

경우 D를 만족하려면 노드 now의 자식에서 노드 next와 next가 아닌 다른 자식 노드를 고르고, 노드 next에서 임의로 하나의 자식을 골라서 이를 연결해야 한다. 따라서 가능한 경우의 수는 next의 자식 노드 개수와 now의 자식 노드 개수에서 1을 뺀 값을 서로 곱한 것과 같다. now의 자식 노드 개수에서 1을 뺀 이유는 ‘ㄷ’ 모양의 트리를 만드는 데 노드 next를 이미 골랐기 때문에 노드 next를 제외한 나머지 자식 노드에서 선택해야 한다.

 

 

 

정리하자면, DFS로 모든 정점을 한 번씩 탐색하면서 각 정점의 자식 노드 수를 구하여 저장한다. 그리고 다시 한 번 DFS를 탐색하면서 각 정점에서 경우 A, B, C, D의 가짓수를 구하고 이를 전체 ‘ㄷ’와 ‘ㅈ’ 트리 개수에 추가하면 된다.

 

참고로 코드에서는 경우 C의 가짓수를 구할 때 현재 방문 중인 노드인 now를 기준으로 구하지 않고 now의 depth가 4보다 크거나 같으면 바로 ‘ㄷ’ 트리 개수에 1을 더했는데, 어차피 탐색 깊이가 4를 넘어가는 이상 위로 ‘ㄷ’ 트리를 한 개 더 찾을 수 있다는 뜻이므로 결과적으로 앞에서 말한 바와 같다.

 

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

const int N_MAX = 3 * (int)1e5;


long long dNum; // 'ㄷ' 트리 개수
long long gNum; // 'ㅈ' 트리 개수
long long depth[N_MAX + 1];
long long childNum[N_MAX + 1];
vector<int> edges[N_MAX + 1];

void go(int now, int parent, int nowDepth){
    depth[now] = nowDepth;
    for (auto next: edges[now]){
        if (next != parent){
            childNum[now] += 1;
            go(next, now, nowDepth + 1);
        }
    }
    return;
}

long long combination(long long n, long long r){
    // r은 2 또는 3만 들어온다고 가정함
    if (n < r) return 0;
    long long t = 1;
    for (long long i = 0; i < r; i++){
        t *= (n - i);
    }
    for (long long i = r; i >= 1; i--){
        t /= i;
    }
    return t;
}

void countTree(int now, int parent){
    if (depth[now] >= 4){
        dNum += 1;
    }
    for (auto next: edges[now]){
        if (next == parent) continue;
        dNum += childNum[next] * (childNum[now] - 1);
        gNum += combination(childNum[next], 2);
        countTree(next, now);
    }
    gNum += combination(childNum[now], 3);
}

int main(){
    int n; scanf("%d", &n);
    
    for (int i = 1; i < n; i++){
        int u, v; scanf("%d %d", &u, &v);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    
    go(1, 0, 1);
    countTree(1, 0);
    
    
    if (dNum > 3 * gNum){
        printf("D\n");
    }
    else if (dNum < 3 * gNum){
        printf("G\n");
    }
    else{
        printf("DUDUDUNGA\n");
    }
    return 0;
}