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

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

11725번: 트리의 부모 찾기

문제 풀이

1. 주어진 입력을 인접 리스트에 저장한다.

2. 루트 노드가 1이므로 1부터 시작하여 BFS 로 탐색한다.

3. BFS 로 탐색 시 next 로 queue 에 저장되는 값이 current 를 parent node 로 같는 정보이다.

코드

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val N = br.readLine().toInt()
    val list = Array(N + 1) { ArrayList<Int>() }

    repeat(N - 1) {
        val (a, b) = br.readLine().split(" ").map { it.toInt() }
        list[a].add(b)
        list[b].add(a)
    }

    bfs(N, list)
}

private fun bfs(N: Int, list: Array<ArrayList<Int>>) {
    val start = 1
    val visit = BooleanArray(N + 1) { false }
    visit[start] = true
    val queue = LinkedList<Int>()
    queue.add(start)
    val result = IntArray(N + 1) { 0 }

    while (queue.isNotEmpty()) {
        val current = queue.pop()
        //println("current : $current, $queue")

        for (next in list[current]) {
            //println("next : $next")

            if (visit[next]) continue

            visit[next] = true
            result[next] = current
            queue.add(next)
        }
    }

    for (i in 2..N) {
        println("${result[i]}")
    }
}