이진 트리( BOJ 31966 )

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

 

문제 파악하기

이진 트리의 모습이 순차적으로 주어질 때, 모든 말단 노드의 순서쌍 (a, b)에 대한 f(a, b) 값의 합인 S(T)를 구하는 문제입니다. f(a, b)는 말단노드 a에서 b까지 모두 덮는데 필요한 노드 최솟값을 의미하며, 문제를 해결하기 위해서는 트리의 왼쪽 서브트리와 오른쪽 서브트리를 입력받을 때마다 f(a, b)의 합을 모두 구해서 출력하면 됩니다. 다만, 트리의 입력이 서브트리의 형태로 주어지기 때문에 개수가 입력 값이 증가할수록 노드의 개수가 기하급수적으로 증가하게 됩니다. 따라서, 이 문제를 해결하기 위해서는 트리의 모습을 모두 구하는 것이 아닌, 미리 구해놓은 값을 활용하는 동적 프로그래밍 기법이 필요합니다.

 

문제 해결하기

그렇다면 어떤 정보를 기록해서 나중에 참고해서 원하는 값을 구할 수 있을까요? 우선, 각각의 서브트리에서 구할 수 있는 S(T)의 값을 저장해야 합니다. 그래야 왼쪽 서브트리에서 구할 수 있는 f(a, b) 값과 오른쪽 서브트리에서 구할 수 있는 f(a, b) 값을 한번에 구할 수 있기 때문입니다. 그리고 여기에 추가로 양쪽(왼쪽, 오른쪽) 서브트리의 노드를 모두 활용하는 값을 구해야 합니다. 이 점이 조금 까다로운데 여기서 초점을 맞춰야 하는 점은 바로 맨 왼쪽과 맨 오른쪽 말단 노드입니다. 양쪽 서브트리의 노드를 모두 활용하기 위해서는 항상 왼쪽 서브트리의 가장 오른쪽 노드와 오른쪽 서브트리의 가장 왼쪽 노드가 사용되기 때문입니다. 그렇기에 우리는 각각의 서브트리에서 맨 왼쪽 서브트리를 포함한 f(a, b)의 값과 맨 오른쪽 서브트리를 포함한 f(a, b)를 각각 저장할 필요가 있습니다. 그리고 이 값을 적절히 활용하면 우리가 원하는 전체 f(a, b)의 합인 S(T)를 구할 수 있습니다. 자세한 소스코드는 다음과 같습니다.

 

소스코드

#include <stdio.h>
#define MOD 1000000007
typedef long long INT;
 
struct Node {
    INT left, right, sz;
    INT ret;
    
    Node(){ left = right = sz = ret = 1; }
};
 
int N, a, b;
Node tree[100010];
 
int main() {
    scanf("%d", &N);
    for(int i=1;i<=N;i++) {
        scanf("%d %d", &a, &b);
        
        // tree[i].ret : S[i] 값
        // tree[a].ret + tree[b].ret : 왼쪽과 오른쪽 자식만 사용한 경우
        // tree[a].right * tree[b].sz + tree[b].left * tree[a].sz : 왼쪽과 오른쪽 자식을 겹쳐서 사용한 경우
        // 1을 빼는 이유 : 예외사항(모든 말단 노드를 포함하는 경우) 처리
        tree[i].ret = (tree[a].ret + tree[b].ret)%MOD;
        tree[i].ret = (tree[i].ret + (tree[a].right * tree[b].sz) + (tree[b].left * tree[a].sz) - 1)%MOD;
        
        // tree[i].sz : 말단 노드의 개수
        tree[i].sz = (tree[a].sz + tree[b].sz)%MOD;
        
        // tree[i].left : 맨 왼쪽 자식을 포함하는 f(a, b)의 값
        // tree[b].left + tree[b].sz : tree[a]를 모두 사용하고, tree[b]의 일부분을 사용할 때의 f(a, b) 값
        // >> tree[a]는 모두 사용하기 때문에 항상 1이며, tree[b]의 말단 노드 개수만큼 1을 더해줌
        tree[i].left = (tree[a].left + (tree[b].left + tree[b].sz) - 1)%MOD;
        
        // tree[i].right : 맨 오른쪽 자식을 포함하는 f(a, b)의 값
        // tree[a].right + tree[a].sz : tree[b]를 모두 사용하고, tree[a]의 일부분을 사용할 때의 f(a, b) 값
        // >> tree[b]는 모두 사용하기 때문에 항상 1이며, tree[a]의 말단 노드 개수만큼 1을 더해줌
        tree[i].right = (tree[b].right + tree[a].right + (tree[a].sz - 1))%MOD;
        
        printf("%lld\n", tree[i].ret);
    }
    
}
 

후기

문제 설명이 조금 난해했지만 문제를 해결하는 과정 자체는 깔끔했던 문제입니다. 트리와 동적 프로그래밍이 결합된 문제들은 항상 깔끔한 느낌이 드는데 이번 문제 역시 깔끔해서 문제를 푸는데 재미있었습니다. 트리에서 동적 프로그래밍을 활용하는 방법을 공부하는 사람에게 추천하고 싶은 문제입니다.