[Kotlin, S1] 백준 1991번 트리 순회

출처: unsplash.com

 

트리 순회(1991번)

Silver 1

#트리 #재귀

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

 

문제 내용

 

 

문제 접근

입력값을 기반으로 트리를 만들어서 전위, 중위, 후위 순회를 한 결과를 출력해야 한다.

트리 문제가 생소한 사람들을 트리를 어떻게 구성해야 하는지부터 난감할 것이다. 내가 그랬다.

트리 구성은 문제 본문에 나와 있는 것 그대로 구성해 볼 생각이다.

먼저 한 노드의 정보를 표시할 Node 데이터를 구성해 줄 것이다. node에는 value와 left, right 데이터가 존재하도록 구현한다.

private data class Node(
    val value: String,
    var left: Node?,
    var right: Node?,
)

left와 right는 하위 Node로 구성되어 있다. nullable 하게 구현한 이유는 루트 노드(트리의 끝)에는 자식 노드인 left, right가 존재하지 않기 때문이다.

 

위와 같이 data class를 구현해 주면 문제 본문의 트리의 노드 하나하나가 Node가 되도록 구성해 줄 수 있고, 트리 변수의 타입도 Node 하나로 정의할 수 있다. List나 Map을 쓸 필요가 없다.

하지만 그만큼 Node를 구성하는 게 쉬운 게 아니다.

 

문제에서 루트 노드는 A로 고정되어 있다고 했기 때문에, tree를 생성해 준다.

private val tree = Node("A", null, null)

이제 데이터를 입력받으면서 right와 left를 채워주면 된다.

 

채우는 경우는 각 노드가 tree의 value와 일치할 때만 채워 줘야 한다. 마침표가 입력되는 경우도 잘 체크해야 한다.

이제 트리를 구성하는 데 필요한 조건들을 알아보자.

조건들은 입력 예제 1을 기반으로 설명한다.

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

 

 

<조건 1>

위에서 언급한 것처럼 들어오는 값의 노드 값이 Node의 value와 일치해야 한다.

private fun insertNode(tree: Node?, value: String, left: String, right: String) {
    if (tree?.value == value) ...
    
    ...
}

위와 같이 설정하면 만약 value가 A가 들어왔을 때, 현재 tree의 value인 A와 일치하기 때문에 A와 같이 입력된 B, C를 각각 left, right에 저장하면 된다.

만약 일치하지 않은 경우에는 어떻게 해야 할까?

 

 

<조건 2>

현재 tree에는 value에는 루트 A가 있고, 하위 Node들 B, C가 있다. 이제 B의 자식을 체크해야 한다. 현재 tree?.value는 A로 설정되어 있어서 조건이 맞지 않는다.

조건 1이 일치하지 않으면 조건 1에 정의한 조건에서 tree?.value를 수정해 줘야 한다. 그래다 다른 값들도 자식 Node를 설정할 수 있을 테니.

조건을 수정하기 위한 조건은 현재 Node의 left 또는 right가 null이 아니어야 한다. 이를 코드로 나타내면 다음과 같다.

if (tree?.left != null) insertNode(tree.left, value, left, right)
if (tree?.right != null) insertNode(tree.right, value, left, right)

현재 A 하위에 B, C Node가 존재하기에 조건이 성립된다. 그러므로 tree에 해당하는 부분을 현재 tree.left로 교체하고 재귀 호출을 한다. right도 마찬가지.

그렇게 재귀 호출을 하면 다시 조건 1부터 다시 보게 되는데 확인할 노드를 A의 하위 노드로 옮겨가는 것이다.

이를 반복하게 되면 모든 데이터를 트리로 구성할 수 있게 된다.

 

재귀 함수를 통해 트리를 구성했으면 나머지는 쉽다.

 

트리를 다시 재귀 호출을 하면서 순회해 주면 된다.

전위 순회를 예로 구현해 보겠다.

전위 순회 순서가 루트 -> 왼쪽 -> 오른쪽 이기 때문에 재귀 함수를 아래와 같이 구성해 준다.

private fun frontTraversal(node: Node?) {
    if (node == null) return

    // 전위 순회: 루트 -> 왼쪽 -> 오른쪽.
    print(node.value)
    frontTraversal(node.left)
    frontTraversal(node.right)
}

먼저 루트를 출력해야 하기 때문에 출력을 먼저 진행하고, 왼쪽으로 그다음은 오른쪽으로 탐색을 진행한다.

먼저 왼쪽 방향으로 가는데, 루트 노드까지 끝까지 진행하고 null이 들어오면 함수가 끝나게 된다.

 

간단하게 탐색 과정을 설명하겠다.

사진 1-1

1. 우선 A부터 시작해 B, D순으로 탐색을 진행한다.

2. D에 도달하게 되면 다음 Node는 null이기 때문에 재귀가 끝나고 남은 tree.right 재귀가 호출된다.

3. C를 출력하고 다시 tree.left 재귀로 들어가서 E를 출력하고 return 된다(다음 Node가 null).

4. 다시 C의 tree.right 재귀를 진행해 F, G로 진행된다(left는 null이라 넘어감).

 

그래서 출력이 ABDCEFG가 된다.

중위, 후위 순회도 전위 순회 함수처럼 재귀로 진행하면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

private val tree = Node("A", null, null)

private data class Node(
    val value: String,
    var left: Node?,
    var right: Node?,
)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    for (i in 0 until case) {
        val (number, left, right) = readLine().split(" ")

        insertNode(tree, number, left, right)
    }

    frontTraversal(tree)
    println()

    middleTraversal(tree)
    println()

    endTraversal(tree)
}

private fun insertNode(tree: Node?, value: String, left: String, right: String) {
    if (tree?.value == value) {
        tree.left = if (left == ".") null else Node(left, null, null)
        tree.right = if (right == ".") null else Node(right, null, null)
    } else {
        if (tree?.left != null) insertNode(tree.left, value, left, right)
        if (tree?.right != null) insertNode(tree.right, value, left, right)
    }
}

private fun frontTraversal(node: Node?) {
    if (node == null) return

    // 전위 순회: 루트 -> 왼쪽 -> 오른쪽.
    print(node.value)
    frontTraversal(node.left)
    frontTraversal(node.right)
}

private fun middleTraversal(node: Node?) {
    if (node == null) return

    // 중위 순회: 왼쪽 자식 -> 루트 -> 오른쪽 자식.
    middleTraversal(node.left)
    print(node.value)
    middleTraversal(node.right)
}

private fun endTraversal(node: Node?) {
    if (node == null) return

    // 후위 순회: 왼쪽 -> 오른쪽 -> 루트.
    endTraversal(node.left)
    endTraversal(node.right)
    print(node.value)
}

 

문제 풀이

Node data class를 생성해 주고 조건 1, 조건 2를 바탕으로 tree 변수에 트리를 구성해 준다.

그리고 전위 순회, 중위 순회, 후위 순회의 결과를 출력한다.

 

 

문제 해결 과정

트리를 구성하는 것도 힘들다.

처음 하는 사람들은 많이 헤맬 수 있다. 내가 그랬다.

나는 트리 구성부터 막혀서 정답을 참고할 수밖에 없었다.

트리를 구성하는 것은 저런 형식을 따른다는 것을 알고 있어야겠다.

 

참고한 블로그 링크도 걸어 놓겠다.

https://stdio-han.tistory.com/138

백준 1991번: 트리 순회[JAVA]