[백준/코틀린] 11725번: 트리의 부모 찾기

링크

11725번: 트리의 부모 찾기

풀이

트리는 사이클이 없는 연결 그래프이므로, 루트 노드에서 탐색을 시작하면
각 노드에 처음 도달한 경로가 곧 그 노드의 부모 노드가 됩니다.

DFS 또는 BFS를 사용해 루트부터 트리를 탐색하며,
각 노드를 처음 방문할 때 그 노드의 부모를 기록합니다.
(트리는 사이클이 없으므로, 모든 노드는 한 번만 방문됩니다.)

코드

lateinit var tree: List<MutableList<Int>>
lateinit var parent: IntArray

fun dfs(start: Int) {
    val stack = ArrayDeque<Int>()

    parent[start] = start
    stack.addLast(start)
    while (stack.isNotEmpty()) {
        val current = stack.removeLast()

        tree[current].forEach {
            if (parent[it] == 0) {
                parent[it] = current
                stack.addLast(it)
            }
        }
    }
}

fun main() {
    val n = readln().toInt()
    tree = List(n + 1) { mutableListOf() }
    parent = IntArray(n + 1)

    repeat(n - 1) {
        val (u, v) = readln().split(" ").map { it.toInt() }

        tree[u] += v
        tree[v] += u
    }

    dfs(1)

    parent.drop(2).forEach { println(it) }
}