백준 2250번: 트리의 높이와 너비 (JAVA)

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

2250번: 트리의 높이와 너비

문제

이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.

1. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다.
2. 한 열에는 한 노드만 존재한다.
3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.
4. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.

아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.

우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.

임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오

입력

첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.

 

 

출력

첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.

 

---

 

풀이 

풀이 1. 내 풀이

트리에 대한 기본 개념만 공부하고 풀이하였다. 현재 node의 위치를 구하려면 현재 node의 left child의 수를 구하면 되기에, root를 구하고(root가 1이 아닐 수도 있다), child를 구하여 left child 수를 구하고, 이후 root에서부터 다시 재귀를 돌면서 각 node의 위치와 높이를 구하였다.

 

풀이 2. 다른 분들의 풀이

중위 탐색하면서 중위 탐색 끝나고 위치를 1씩 더해주면 위치가 구해지더라: 본인 방문이 끝났으니 위치를 하나 더한다는 느낌.

 

 

코드 

 

풀이 1

import java.io.*;
import java.util.*;

public class Main {
    static int ans, N;
    static int[] p, l, r, lc, rc, c, level;
    static boolean[] visited;
    static List<List<Integer>> widths;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        p = new int[N+1];
        l = new int[N+1];
        r = new int[N+1];
        // lc, rc, c: 해당 노드의 left child, right child, child 수
        lc = new int[N+1];
        rc = new int[N+1];
        c = new int[N+1];
        visited = new boolean[N+1];
        level = new int[N+1];
        // widths의 i번째 index에는 level이 i인 node의 위치들을 저장한다.
        widths = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            widths.add(new ArrayList<Integer>());
        }

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            if (left != -1) {
                p[left] = cur;
            }
            l[cur] = left;
            if (right != -1) {
                p[right] = cur;
            }
            r[cur] = right;
        }

        // forest가 아니라면 하나의 루트를 찾게 됨.
        int root = findRoot(1);

        // 자식 수 구하기
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                children(i);
            }
        }

        // root 기준으로 level과 위치 구하기
        calc(0, root, 1);

        // 최대 폭인 level과 widht 구하기
        int level = 1;
        int ansWidth = 0;
        int ansLevel = 0;
        while (level <= N && !widths.get(level).isEmpty()) {
            // 정렬이 되어있음
            // 빈 array가 나온다 -> 그 다음 level인 node는 존재할 수 없음.
            int min = widths.get(level).get(0);
            int max = widths.get(level).get(widths.get(level).size()-1);
            if (ansWidth < max - min + 1) {
                ansWidth = max - min + 1;
                ansLevel = level;
            }
            level++;
        }
        System.out.println(ansLevel+" "+ansWidth);
    }
	
    // root를 찾는 method
    static int findRoot(int cur) {
        if (p[cur] != 0) return findRoot(p[cur]);
        else return cur;
    }
	
    // 현재 node의 left child, right child 수를 구하는 method
    static int children(int cur) {
        if (visited[cur]) return c[cur];
        if (l[cur] != -1) {
            lc[cur] += children(l[cur]) + 1;
        }
        if (r[cur] != -1) {
            rc[cur] += children(r[cur]) + 1;
        }
        c[cur] = lc[cur] + rc[cur];
        visited[cur] = true;
        return c[cur];
    }
	
    // 현재 node의 위치, level을 구하는 method
    static void calc(int prevs, int cur, int level) {
        widths.get(level).add(prevs+lc[cur]+1);
        if (l[cur] != -1) calc(prevs, l[cur], level+1);
        if (r[cur] != -1) calc(prevs+lc[cur]+1, r[cur], level+1);
    }
}

 

풀이 2

import java.io.*;
import java.util.*;

public class Main {	
    static int ans, N, row = 1;
    static int[] p, l, r, min, max;
    static boolean[] visited;
    static List<List<Integer>> widths;
    static int ansWidth = 0;
    static int ansLevel = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        p = new int[N+1];
        l = new int[N+1];
        r = new int[N+1];
        // min, max: level에 대하여 위치값의 최소, 최대를 저장하는 배열
        min = new int[N+1];
        Arrays.fill(min, 20000);
        max = new int[N+1];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());
            if (left != -1) {
                p[left] = cur;
            }
            l[cur] = left;
            if (right != -1) {
                p[right] = cur;
            }
            r[cur] = right;
        }

        int root = findRoot(1);
        inorder(root, 1);
        
        for (int i = 1; i <= N; i++) {
            if (ansWidth < max[i] - min[i] + 1) {
                ansWidth = max[i] - min[i] + 1;
                ansLevel = i;
            }
        }
        System.out.println(ansLevel+" "+ansWidth);
    }

    static int findRoot(int cur) {
        if (p[cur] != 0) return findRoot(p[cur]);
        else return cur;
    }

    static void inorder(int cur, int level) {
        if (cur != -1) {
            inorder(l[cur], level+1);
            // 현재 node 방문하였으면, 이후 방문하는 node는 현재 node보다 뒤에 있음
            min[level] = Math.min(min[level], row);
            max[level] = Math.max(max[level], row);
            row++;
            inorder(r[cur], level+1);
        }
    }
}