[백준] 2250 트리의 높이와 너비 - Graph Theory / Java

• 문제 링크

2250번: 트리의 높이와 너비

 

• 풀이 과정

각 층(level) 에 존재하는 노드의 간격의 최대, 최소값을 저장할 max, min 배열을 생성하여

각 층마다 0, n(노드의 개수) 값으로 초기화한다.

 

문제에 주어진 트리를 부모, 현재, 왼쪽 자식, 오른쪽 자식 노드의 값을 가진 Node 객체 배열을 통해 구성하며,

각각의 왼쪽, 오른쪽 자식 노드의 존재 여부에 따라 현재 노드를 부모 노드로 지정한다.

 

이 중 부모 노드가 없는 노드를 찾아 해당 노드를 루트 노드로써 탐색을 시작한다.

조건상 중위 순회(inorder) 를 통해 좌측부터 탐색하며,

각 층에서의 너비의 최대, 최소값을 갱신하여 max, min 배열에 저장한다.

 

이렇게 구해진 각 층의 너비 중 최대값을 가지는 층과 해당 값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    static int maxLevel;
    static int row = 1;
    static Node[] nodes;
    static int[] max, min;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        nodes = new Node[n + 1];
        max = new int[n + 1];
        min = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            nodes[i] = new Node(i);
            max[i] = 0;
            min[i] = n;
        }

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int cur = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            nodes[cur].left = left;
            nodes[cur].right = right;

            if (left != -1)
                nodes[left].parent = cur;
            if (right != -1)
                nodes[right].parent = cur;
        }

        for (int i = 1; i <= n; i++) {
            if (nodes[i].parent == -1) {
                inorder(i, 1);
                break;
            }
        }

        int level = 0;
        int maxWidth = 0;
        for (int i = 1; i <= maxLevel; i++) {
            int width = max[i] - min[i] + 1;
            if (maxWidth < width) {
                maxWidth = width;
                level = i;
            }
        }

        bw.write(level + " " + maxWidth);
        bw.flush();
    }

    private static void inorder(int node, int level) {
        Node cur = nodes[node];

        maxLevel = Math.max(maxLevel, level);

        if (cur.left != -1)
            inorder(cur.left, level + 1);

        min[level] = Math.min(min[level], row);
        max[level] = row++;

        if (cur.right != -1)
            inorder(cur.right, level + 1);
    }

    private static class Node {
        int parent, cur, left, right;

        public Node(int cur) {
            this.cur = cur;
            parent = left = right = -1;
        }
    }

}