[백준 14725] 개미굴 (Kotlin)

🏆 문제 난이도
- Gold III

🔗 문제 링크
https://www.acmicpc.net/problem/14725

📝 문제 분석 & 접근

문제를 해결하기 위해 가장 먼저 떠올릴 수 있는 아이디어는 트리(Tree) 자료구조를 사용하는 것입니다.

각 경로의 문자열을 트리의 노드로 삼아 연결하는 방식입니다

• 루트 노드(Root Node): 개미굴의 시작점을 나타내는 가상의 루트 노드를 만듭니다.
• 자식 노드(Child Nodes): 각 경로의 문자열은 부모 노드의 자식 노드가 됩니다.
• 동일 경로: 만약 이미 존재하는 경로가 다시 입력으로 들어오면, 새로운 노드를 추가하는 대신 기존 노드를 따라가야 합니다.

예를 들어, A -> B 경로가 추가된 후, 다시 A -> C 경로가 들어온다면, 루트 노드에서 A 노드를 찾고, A 노드의 자식으로 C 노드를 추가하는 식입니다.

A -> B -> D처럼 더 깊은 경로가 들어오면, A -> B 노드를 순서대로 찾아가면서 B 노드의 자식으로 D 노드를 추가합니다.

이렇게 모든 경로를 트리로 구성한 후에는, 깊이 우선 탐색(DFS, Depth-First Search)을 사용하여 트리를 탐색하면서 원하는 형식으로 출력하면 됩니다.

이때, 문제에서 요구하는 사전 순 정렬을 지켜야 합니다.

---

✨ 핵심 아이디어

1. 트리 구축

• 각 경로의 문자열을 트리의 노드로 나타냅니다.
• 노드 클래스(Node)에는 노드의 이름(feed)과 자식 노드들을 저장할 컬렉션이 필요합니다.
• 이때, 자식 노드들은 자동으로 정렬되어야 합니다.
• Kotlin에서는 TreeSet을 사용하면 노드를 Comparable로 구현하여 이 조건을 쉽게 만족시킬 수 있습니다.
• 입력으로 들어오는 경로를 순서대로 읽으면서 트리를 만듭니다.
• 현재 노드의 자식 중에 다음 경로 문자열과 일치하는 노드가 있다면 그 노드로 이동하고, 없다면 새로운 노드를 만들어 추가한 후 이동합니다.

2. 깊이 우선 탐색(DFS)

• 트리 구축이 끝나면, 가상의 루트 노드부터 DFS를 시작합니다.
• DFS를 수행하면서 현재 탐색 중인 노드의 깊이(depth)를 추적합니다.
• 깊이에 따라 --를 반복해서 출력하고, 그 뒤에 노드의 이름을 출력합니다.
• 노드의 자식들을 순회하며 재귀적으로 DFS를 호출합니다.
• TreeSet은 요소를 추가할 때 자동으로 정렬되기 때문에, for-each 반복문을 사용하면 이미 사전 순으로 정렬된 상태의 자식들을 순회하게 됩니다. 따라서 DFS만으로 문제의 요구사항인 사전 순 출력이 자연스럽게 해결됩니다.

TreeSet vs. PriorityQueue (PQ)

처음에 저는 TreeSet 대신 PriorityQueue를 사용하여 자식 노드를 관리하는 실수를 했습니다.
이 문제에서 priorityQueue를 사용하여 자식 노드를 관리할 경우에 for문을 사용한 순회에서 정렬 상태가 유지되지 않아 제출해도 3%에서 틀렸다고 뜰껍니다.

• TreeSet: 이진 탐색 트리 기반의 자료구조로, 요소를 삽입할 때마다 자동으로 정렬 상태를 유지합니다. 따라서 for-each 문으로 순회하면 항상 정렬된 순서대로 요소를 얻을 수 있습니다.
• PriorityQueue: 힙(Heap) 기반의 자료구조로, 가장 우선순위가 높은(우선순위 큐에서는 가장 작은) 요소를 빠르게 가져오는 데 특화되어 있습니다. 하지만 for 문으로 PriorityQueue를 순회하면 내부적으로 힙 정렬이 보장되지 않아, 정렬되지 않은 순서로 요소가 반환될 수 있습니다. 문제의 요구사항인 사전 순 출력을 위해서는 TreeSet과 같이 순회 시 정렬 순서가 보장되는 자료구조를 사용해야 합니다.

---

💻 코드

import java.io.StreamTokenizer
import java.util.TreeSet

data class Node(
    val feed: String,
    val sibling : TreeSet<Node> = TreeSet()
) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return feed.compareTo(other.feed)
    }
}

val sb = StringBuilder()

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun StreamTokenizer.nextInt(): Int {
        nextToken()
        return nval.toInt()
    }

    fun StreamTokenizer.nextString(): String {
        nextToken()
        return sval
    }

    val n = nextInt()
    val root = Node("root")

    repeat(n) {
        val depth = nextInt()
        var parent = root
        repeat(depth) {
            val feed = nextString()
            val child = parent.sibling.find { it.feed == feed }
            if (child != null) {
                parent = child
            } else {
                val newNode = Node(feed)
                parent.sibling.add(newNode)
                parent = newNode
            }
        }
    }

    dfs(root)
    println(sb)
}

fun dfs(node: Node, depth: Int = -1) {
    if (node.feed != "root") {
        repeat(depth) { sb.append("--") }
        sb.append(node.feed).append("\n")
    }
    for (child in node.sibling) {
        dfs(child, depth + 1)
    }
}