[백준/BOJ] 11725번: 트리의 부모 찾기

문제

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

11725번: 트리의 부모 찾기

해설

DFS를 이용하여 해결할 수 있는 문제이다.

트리 상에 연결되는 두 정점이 부모-노드 구분이 없기 때문에 양방향으로 넣어줘야한다.

또한 문제에서 트리의 루트를 1이라고 정했기 때문에, 1은 먼저 방문처리 해준 후, DFS를 실행시킨다.

소스 코드

private lateinit var arr: Array<ArrayList<Int>>
private lateinit var parent: IntArray
private lateinit var visited: BooleanArray

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()

    arr = Array(n + 1) { ArrayList() }
    parent = IntArray(n + 1)
    visited = BooleanArray(n + 1)

    repeat(n-1) {
        val (node1, node2) = readLine().split(" ").map { it.toInt() }
        arr[node1].add(node2)
        arr[node2].add(node1)
    }

    find(1)

    for(i in 2 .. n) println(parent[i])
}

private fun find(n: Int) {
    visited[n] = true
    for(i in 0 until arr[n].size) {
        val next = arr[n][i]

        if(!visited[next]) {
            parent[next] = n
            find(next)
        }
    }
}