[백준][2250번] 트리의 높이와 너비

문제 URL

https://www.acmicpc.net/problem/2250

트리의 순회

트리의 순회 방법에는 3가지 종류가 있다.

1. 프리오더
   • 노드방문
   • 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더
   • 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더
2. 인오더
   • 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더
   • 노드방문
   • 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더
3. 포스트오더
   • 왼쪽 자식 노드를 루트로 하는 서브 트리 프리오더
   • 오른쪽 자식 노드를 루트로 하는 서브 트리 프리오더
   • 노드방문

*자식의 정보를 이용해서 현재의 계산을할때 포스트오더 사용! 반면, 부모의 정보를 이용해서 자식의 정보를 이용하면 프리오더

전체 풀이

이 문제의 경우 트리의 순회 방법 중 ‘인오더’ 방식을 사용한다. 한 노드를 기준으로 왼쪽 자식노드가 끝나야 자신노드의 열을 채워넣을 수 있기때문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static class Node {
        int left, right;
        Node(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    public static Node[] a;
    public static int cnt = 0;
    public static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        a = new Node[n+1];
        // dp[i][j]
        // i : 깊이
        // j : 0 - 해당 깊이의 최솟값 1 - 최댓값
        dp = new int[n+1][2];
        //루트노드 구하기위한 변수
        int[] cnt = new int[n+1];

        for(int i=0; i<=n; i++){
            for(int j=0; j<2; j++){
                dp[i][j] = -1;
            }
        }

        for(int i=0; i<n; i++){
            StringTokenizer stk = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());
            int z = Integer.parseInt(stk.nextToken());
            a[x] = new Node(y, z);
            if(y!=-1) cnt[y] += 1;
            if(z!=-1) cnt[z] += 1;
        }

        //루트노드 구하는 과정
        int root=0;
        for(int i=1; i<=n; i++){
            if(cnt[i] == 0){
                root = i;
            }
        }
        cal(root, 1);

        int maxDepth = 0;
        int maxNum = 0;
        for(int i=1; i<=n; i++){
            if(dp[i][1] == -1)
                break;

            int m = dp[i][1] - dp[i][0] + 1;
            if(maxNum < m){
                maxNum = m;
                maxDepth = i;
            }
        }
        System.out.println(maxDepth +" " + maxNum);
    }

//인오더 방식의 트리순회방식
    public static void cal(int x, int depth){
        if(x == -1) return;

        cal(a[x].left, depth+1);

//cnt는 열을 뜻한다.
        cnt++;
        if(dp[depth][0] == -1)
            dp[depth][0] = cnt;
        dp[depth][1] = cnt;

        cal(a[x].right, depth+1);
    }
}

느낀점

처음에 틀렸던 이유는 루트노드를 무의식적으로 1로 가정하고 풀었다. 문제 예시에서도 그랬어서 1이 당연히 루트노드라고 생각한 실수를 저질렀다.

1이 루트노드가 아닐 수 있으므로 직접 구하는방식으로 풀었다.