[백준][코틀린][2250] 트리의 높이와 너비

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

2250번: 트리의 높이와 너비

문제 풀이

1. 이진 트리를 구성하여 주어진 입력을 트리에 넣는다.

2. 주어진 문제에는 루트 노드가 1이지만 조건에 루트 노드가 항상 1이라는 내용이 없기 때문에 이진 트리를 구성하고 어떤 값이 루트 노드인지를 찾아야 한다.

3. 이진 트리 구성 지 루트 노드를 찾기 위해서 노드 Data Class 를 다음과 같이 구성한다.

Node(val parent, val num, val left, val right

- parent : 현재 노드의 부모 노드 저장

- num : 현재 노드 값 저장

- left : 현재 노드의 왼쪽 노드 저장

- right : 현재 노드의 오른쪽 노드 저장

4. 중위 순회(왼쪽 -> 루트 -> 오른쪽) 를 이용할 경우 주어진 문제의 조건에 따라 노드들을 순서대로 찾을 수 있다.

5. 중위 순회 시 각 노드의 depth 를 parameter 로 넘겨주고 루트를 검색할 때 마다 index 를 증가하여 검색된 노드의 위치를 찾는다.

6. 최대/최소 값을 Int 배열로 선언하고 depth 의 최대/최소 값을 저장한 뒤 출력 조건에 맞게 가장 큰 차이 값을 출력한다.

코드

import java.io.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val tree = Tree2250(N)

    for (i in 0..N) {
        tree.root.add(i, Node2250(-1, i, -1, -1))
    }

    repeat(N) {
        val (a, b, c) = br.readLine().split(" ").map { it.toInt() }
        tree.add(a, b, c)
    }

    // tree 에 정보들이 잘 들어 갔는 지 확인 한다.
    /*tree.root.forEach {
        println("${it.parent}, ${it.num}, ${it.left}, ${it.right}")
    }*/


    // root index 를 찾는다.
    var rootIndex = -1

    for (i in 1..N) {
        if (tree.root[i].parent == -1) {
            rootIndex = i
            break
        }
    }

    //println("rootIndex : $rootIndex")


    // 중위 순회(왼쪽 -> 루트 -> 오른쪽) 수행한다.
    tree.inOrder(rootIndex, 0)

    // 결과를 출력한다.
    tree.getResult()
}

private data class Node2250(
    var parent: Int = -1,
    var num: Int = -1,
    var left: Int = -1,
    var right: Int = -1
)

private class Tree2250(private val n: Int) {
    val root = mutableListOf<Node2250>()
    var min = IntArray(n + 1) { Int.MAX_VALUE }
    var max = IntArray( n + 1) { 0 }
    var index = 0

    fun add(num: Int, left: Int, right: Int) {
        root[num].left = left
        root[num].right = right

        if (left != -1) root[left].parent = left
        if (right != -1) root[right].parent = right
    }

    fun inOrder(rootIndex: Int, depth: Int) {
        val idx = depth + 1
        if (root[rootIndex].left != -1) inOrder(root[root[rootIndex].left].parent, idx)
        index++
        min[idx] = Math.min(min[idx], index)
        max[idx] = index
        //print("${root[rootIndex].num}/($idx, ${min[idx]}, ${max[idx]}) ")
        if (root[rootIndex].right != -1) inOrder(root[root[rootIndex].right].parent, idx)
    }

    fun getResult() {
        var result = Int.MIN_VALUE
        var resultIndex = 0
        for (i in 1..n) {
            //println("$i = ${min[i]}, ${max[i]}")
            if (result < (max[i] - min[i] + 1)) {
                result = (max[i] - min[i] + 1)
                resultIndex = i
            }
        }

        println("$resultIndex $result")
    }
}