백준 11725 트리의 부모 찾기

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

1이 루트인 트리가 주어지고, 각 노드의 부모를 순서대로 출력하는 문제이다.

처음 시도할 때 트리로 나타내는 대신 queue를 이용해 IntArray에 부모 정보를 저장하며 입력의 한 줄에 해당하는 두 수들 중 하나가 부모정보가 있다면 다른 하나를 그 자식으로 만드는 방법을 사용하였다.
(만약 둘 다 부모정보가 없다면 queue에 다시 넣음)

이 예제를 예로 들어본다면

(1, 6)을 받았는데 1은 루트이므로 부모가 있다고 설정(parent[1] = 1), 따라서 6의 부모를 1로 지정함.

(6, 3)을 받았는데 6의 부모가 1이므로 3의 부모를 6으로 지정

(3, 5)를 받았는데 3의 부모가 6이므로, 5의 부모를 3으로 지정

이를 반복하는데, 두 수 모두 부모가 없다면 큐의 뒤로 보냄을 반복.

이 방법이 가능하기는 하지만, N의 범위가 최대 100,000이라는 점을 간과했다.

예를 들어, N이 100,000이고 받은 트리가 LinkedList 형태의 일렬 구조이며 입력 순서가 거꾸로일 경우, 10만줄을 한 번 순회하고 하나 처리하고를 반복하여 시간이 굉장히 오래 걸릴수 있었다.

이를 깨닫고 트리를 인접 리스트 형식으로 나타내어 1번 노드부터 순회하며 부모 정보를 저장하는 방식으로 바꾸기로 하였다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val vertexes = Array(N - 1){readLine().split(' ').map{it.toInt()}}

    val links = Array(N + 1){ LinkedList<Int>() }
    val parents = IntArray(N + 1){-1}
    val visited = BooleanArray(N + 1){ false }
    parents[1] = 1
    visited[1] = true
    vertexes.forEach {
        links[it[0]].add(it[1])
        links[it[1]].add(it[0])
    }

    fun dfs(n: Int){
        for(num in links[n]){
            if(!visited[num]) {
                visited[num] = true
                parents[num] = n
                dfs(num)
            }
        }
    }

    dfs(1)

    val answer = StringBuilder()
    for(i in 2..N){
        answer.append("${parents[i]}\n")
    }
    print(answer.toString())
}

트리를 인접 리스트로 나타낼 links와 부모 정보를 갱신할 parents, 순회에 사용할 방문체크용 visited를 준비하였다.

dfs는 단순히 1번부터 시작하여 현재 노드의 자식들의 부모 정보를 현재 노드로 설정하고 방문체크하는 것이 전부이다.

정답은 parents 배열을 2번부터 N까지 순서대로 출력하면 된다.

여기서, 표준 출력으로 10만개를 출력하는 것보다 StringBuilder를 이용해 한 번에 모아 출력하는 편이 해당 사이트에서는 빠른 것 같다.