[백준] 2250. 트리의 높이와 너비 (자바 JAVA)

문제

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

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

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

예제 출력 1

3 18

힌트

실제 기출문제의 문제 제목은 "이진트리의 너비" 이다.

 

 

접근 방법 🧐

입력값을 바탕으로 트리를 만들고 어떤 아이디어로 접근할지를 생각하는 것이 중요하다.

 

우선 트리의 각 노드를 다음과 같은 클래스로 만들었다.

static class Node {
    int parent; // 부모 번호
    int number; // 자신의 번호
    int leftChild; // 왼쪽 노드 번호
    int rightChild; // 오른쪽 노드 번호

    public Node(int number, int leftChild, int rightChild) {
        this.parent = -1;
        this.number = number;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }
}

 

Node를 만들 때 우선 모든 parent를 -1로 설정해야 한다. 이 문제에서 루트 노드는 무조건 1부터 시작한다는 표현이 없기 때문이다. 따라서 루트 노드의 번호가 2, 3 또는 100일 수도 있다.

그래서 각 Node마다 parent를 -1로 초기화해놓고 입력값을 바탕으로 각 Node에 값을 할당할 때, parent값을 바꿔줄 것이다. 그러면 나중에 루트 Node를 찾을 때 편하다.

모든 노드 중에 parent가 변하지 않고 여전히 -1인 것을 찾으면, 그게 바로 루트 노드가 되는 것이다.

그리고 필요한 것은 각 레벨(깊이)그룹마다 제일 왼쪽에 있는 값의 x좌표 값과, 제일 오른쪽에 있는 값의 x좌표 값이다.

예를 들면 level 2의 가장 왼쪽 좌표는 3이고, 가장 오른쪽 좌표는 15이므로 너비(width)는 15 - 3 + 1이 된다.

즉, 모든 level마다 너비(width)를 구하고 그 중 가장 넓은 값을 출력해야 한다.

그래서 각 level마다 좌표의 최소, 최댓값을 저장해야 한다.

그 값들은 아래의 변수에 저장할 것이다.

static int[] levelMin;
static int[] levelMax;

결국 트리를 천천히 순회하면서 각 레벨의 최소 x좌표, 최대 x좌표 값만 찾으면 된다.

 

트리 순회 방법

트리 순회 방법에는 3가지 방법이 있다.

1. 전위 순회 (루트 -> 왼쪽 -> 오른쪽)
2. 중위 순회 (왼쪽 -> 루트 -> 오른쪽)
3. 후위 순회 (왼쪽 -> 오른쪽 -> 루트)

 

이 3가지 방법 중에 하나로 트리를 순회해야 하는데 이 문제에서는 중위 순회가 적절한 방법이 될 것이다!

왜냐하면 트리를 순회하며 모든 Node들을 방문해야 하는데,

중위 순회는 가장 먼저 방문하는 Node가 가장 왼쪽 노드이기 때문이다.

가장 먼저 방문한 Node의 좌표를 1로 설정한다면 두 번째 방문하게 되는 Node는 좌표가 2일 것이다.

중위 순회를 하면 방문하는 순서 그대로가 각 Node의 x좌표가 된다!

위의 예시를 보면, 중위 순회로 인해 가장 먼저 방문하는 Node는 8이고, 이를 x좌표 1로 설정한다.

그 다음 방문은 4이고 x좌표는 아까의 좌표에서 1 높게 설정하면 된다.

결국 우리는 중위 순회를 하면서 그 Node가 level이 몇이고,

현재 이 Node의 x좌표 값이 동일한  level에서 가장 왼쪽 값인지, 가장 오른쪽 값인지만 판단하면 된다.

그리고 가장 왼쪽 값이거나 가장 오른쪽 값이면 위에서 선언했던 levelMin[] 배열 또는 levelMax[]을 업데이트해주면 된다.

 

 

내가 쓴 코드 ✍️

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

public class Main {
    static class Node {
        int parent;
        int number;
        int leftChild;
        int rightChild;

        public Node(int number, int leftChild, int rightChild) {
            this.parent = -1;
            this.number = number;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }
    }

    private static int current = 1; // 현재 탐색중인 노드 위치, 노드를 방문할 때마다 +1 증가
    private static int maxLevel; // 트리의 최대 레벨(깊이)
    private static int[] levelMin, levelMax;
    private static Node[] nodes;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        nodes = new Node[N + 1];

        levelMin = new int[N + 1];
        levelMax = new int[N + 1];

        for(int i = 0; i <= N; i++) {
            nodes[i] = new Node(i, -1, -1);
            levelMin[i] = N;
            levelMax[i] = 0;
        }

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            int leftChild = Integer.parseInt(st.nextToken());
            int rightChild = Integer.parseInt(st.nextToken());

            nodes[number].leftChild = leftChild;
            nodes[number].rightChild = rightChild;

            if (leftChild != -1) nodes[leftChild].parent = number;
            if (rightChild != -1) nodes[rightChild].parent = number;
        }

        int rootNodeNumber = 0;

        for (int level = 1; level <= N; level++) {
            if (nodes[level].parent == -1) {
                rootNodeNumber = level;
                break;
            }
        }

        inOrderTraversal(rootNodeNumber, 1);

        int answerLevel = 1;
        int answerWidth = levelMax[1] - levelMin[1] + 1;
        for (int level = 2; level <= maxLevel; level++) {
            int width = levelMax[level] - levelMin[level] + 1;
            if (answerWidth < width) {
                answerLevel = level;
                answerWidth = width;
            }
        }

        System.out.println(answerLevel + " " + answerWidth);
    }

    private static void inOrderTraversal(int rootNodeNumber, int level) {
        Node rootNode = nodes[rootNodeNumber];

        if (maxLevel < level) maxLevel = level;

        if (rootNode.leftChild != -1) {
            inOrderTraversal(rootNode.leftChild, level + 1);
        }

        levelMin[level] = Math.min(levelMin[level], current);
        levelMax[level] = current;

        current++;

        if (rootNode.rightChild != -1) {
            inOrderTraversal(rootNode.rightChild, level + 1);
        }
    }
}

 

 

 

구독과 공감♡♡은 블로그 운영에 큰 힘이 됩니다!
긍정적인 댓글 남겨주시면 감사드리며,
보완해야 할 점이 있으면 댓글로 남겨주셔도 좋습니다!