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

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

2250번: 트리의 높이와 너비

 

난이도 : 골드 2
태그 : 그래프이론, 그래프탐색, 깊이 우선 탐색, 트리

 

 

설명

 

해당 문제 같은 경우는 DFS + Inorder(중위순회) 를 통해 구현할 수 있겠습니다.

 

 

 

 

위와 같은 노드가 있다고 가정해봤을때, 이를 인오더로 탐색하면 어떻게 될까요?

 

 

 

7-4-8-2-1-5-3-6-9 순으로 방문을 하게 됩니다.

즉, 좌-부모-우 순으로 탐색을 하기 때문에 좌측에 노드가 있을 경우 부모 노드보다 먼저 방문을 합니다.

 

 

 

 

인오더 탐색 : 8-4-2-14-9-18-15-5-10-1-16-11-6-12-3-17-19-13-7 이 됩니다.

중위순회는 부모가 중간에 오는 트리 탐색 방법으로, 좌측 노드 - 부모 노드 - 우측 노드 순으로 방문하므로,

인오더의 방문 순서가 곧 열의 순서가 됩니다.

이를 잘 활용하면 풀 수 있겠죠?

 

이 문제를 풀며 실수하기 쉬운 점은 루트가 1번이 아닐 수 있다는 점 입니다.

때문에 저는 자식 노드에서 부모 노드의 번호를 지정해 줌으로써,

최종적으로 부모 노드가 지정되지 않은 노드가 루트임을 확인하였습니다.

 

 

접근방법

1. 부모 노드와 좌측노드, 우측 노드를 입력 받으며

   부모 노드에 좌, 우측 노드 지정, 좌,우측 노드에 부모를 지정

2. 누군가의 자식 노드면 부모 노드가 지정되어 있음 -> 부모 노드가 없으면 그 노드가 루트!

3. 인오더 탐색 수행 : 좌측 노드 -> 부모 노드 -> 우측 노드로 탐색하며 해당 노드 번호에 몇 번째 dfs가 몇 번째 수행됬는지 체크

4. 각 레벨의 너비를 구하며 가장 큰 너비와 레벨을 출력

 

 

 

소스코드

package baekjoon.gold.g2.트리의높이와너비

import java.util.StringTokenizer

data class Node(
    val n: Int, // 노드 번호
    var parent: Int = -1, // 부모 노드 번호
    var left: Int = -1, // 좌측 노드 번호
    var right: Int = -1, // 우측 노드 번호
    var colIdx: Int = -1, // 열 인덱스
    var depth: Int = -1 // 깊이(레벨)
)

lateinit var nodes: Array<Node>
var cnt = 1

fun main() = with(System.`in`.bufferedReader()) {

    val n = readLine().toInt()
    nodes = Array(n + 1) { Node(it) } // 0 번째 노드는 미사용

    repeat(n) {
        val st = StringTokenizer(readLine())
        val (parentNode, leftNode, rightNode) = Array(3) { st.nextToken().toInt() }

        if (rightNode != -1) {
            nodes[parentNode].right = rightNode // 현재 노드의 우측 노드 설정
            nodes[rightNode].parent = parentNode // 우측 노드의 부모 노드를 현재 노드로 설정
        }

        if (leftNode != -1) {
            nodes[parentNode].left = leftNode // 현재 노드의 좌측 노드 설정
            nodes[leftNode].parent = parentNode // 좌측 노드의 부모 노드를 현재 노드로 설정
        }
    }

    val root = nodes.indexOfLast { it.parent == -1 } // 부모가 없는 노드 찾기. 0번째 인덱스의 노드도 부모가 없으므로 맨 뒤 부터 찾음

    dfs(root, 1)

    var resultBinary = 0
    var resultLevel = 0

    // 1 레벨부터 최대 깊이 레벨까지 반복
    for (level in 1..nodes.maxOf { it.depth }) {

        val nowLevelNodes = nodes.filter { it.depth == level } // 현재 레벨의 노드만 필터링
        val binary = nowLevelNodes.maxOf { it.colIdx } - nowLevelNodes.minOf { it.colIdx } + 1 // 현재 레벨의 최대 열 번호 - 현재 레벨의 최소 열 번호

        if (resultBinary < binary) {
            resultBinary = binary
            resultLevel = level
        }
    }

    println("$resultLevel $resultBinary")
}

fun dfs(idx: Int, depth: Int) {
    if (idx == -1) return

    // 좌측 노드 - 현재 노드 - 우측 노드 순으로 탐색

    dfs(nodes[idx].left, depth + 1)

    nodes[idx].colIdx = cnt++ // 열 정보 저장
    nodes[idx].depth = depth // 깊이 정보 저장

    dfs(nodes[idx].right, depth + 1)
}

 

코틀린의 람다식을 잘 활용하면, 특정 레벨의 노드만 필터링하거나 열의 최댓값, 최솟값을 쉽게 구할 수 있습니다.

 

 

 

후기

꽤 재밌는 트리문제 였습니다.

풀면서 레벨이랑 깊이도 저장해야 하고... 부모도 체크해줘야겠네... 하면서

꽤 코드가 지저분해질까 걱정했는데, 코틀린의 람다식을 활용하니 생각보다 깔끔히 나와 만족스럽네요.