[Kotlin] 백준 11725번 : 트리의 부모 찾기 <Silver 2>

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

11725번: 트리의 부모 찾기

Code

---

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))
    val N = readLine().toInt()
    val graph = Array(N + 1) { LinkedList<Int>() }
    val parent = IntArray(N + 1)
    val visited = BooleanArray(N + 1) { false }

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

    visited[1] = true
    dfs(graph, visited, parent, N,1)

    for (i in 2..N)
        bw.write("${parent[i]}\n")

    bw.flush()
    bw.close()
}


fun dfs(graph: Array<LinkedList<Int>>, visited: BooleanArray, parent: IntArray,N: Int, now: Int) {
    graph[now].forEach{
        if (!visited[it]) {
            visited[it] = true
            parent[it] = now
            dfs(graph, visited, parent, N, it)
        }
    }
}

---

생각보다 문제 해결하는데 시간이 걸렸다.

 

내가 빠진 함정은 총 두가지가 있다. 순서대로 설명한 후 내가 내린 정답 코드를 설명하겠다.

 

첫 번째 함정은 반복수(최대 노드의 개수)이다.

내 첫번째 아이디어는 값을 입력받고, 두 값 중 하나는 나왔었고, 하나는 나온적 없다면 나온적 없는 숫자의 부모가 나머지 한 숫자가 되는 방식이다. 

1 6이 나왔다면 1은 기본값이기때문에 6의 부모는 1이 된다.

이후 6 3이 나왔다면 6은 나왔었고, 3은 나온적 없기 때문에 3의 부모는 6이 된다.

 

이러한 방식으로 진행되며, 순서대로 나오지 않을 경우를 대비해 둘다 나온 적 없을경우 Queue에 저장해뒀다가 Queue가 전부 빌때까지 순서쌍을 찾아주었다.

 

정답은 잘 찾아진다. 그런데 내가 생각하지 못한것은 최대 노드의 갯수다.

최대 100000개가 주어진다고 하는데, 이때 전부 역순으로 주어진다면 엄청나게 반복하게 된다.

당연히 엄청난 시간이 필요해지기 때문에 틀렸다 ㅋㅋ

 

그래서 묘수병 버리고 BFS를 쓰기로 했다.

 

 

내가 빠진 두 번째 함정은 메모리이다.

위에있는 결과물과 같은 로직을 사용했다. 근데 왜 메모리가 터졌냐.

 

첫번째 함정에서 겪었으면서 또 최대 노드 개수를 고려안했다. N+1칸으로 2차원 배열을 선언하고, N칸의 Queue를 선언하고 BFS로 풀어버리니까... 엄청나게 많은 칸을 만들어서 터졌다 ㅋㅋ

 

그래서 생각한 것이 LinkedList였다.

모든 칸을 만드는 것이 아니라, 해당되는 양만큼만 공간을 만들어줬다.

또한 메모리로 한번 터져서 그런가 BFS로 만들어지는 Queue가 아까워져 DFS로 구현했다.

재귀함수 호출하면 거기서 거기 아닌가...?

 

 

그래서 결과물은?

값을 입력받고, LinkedList로 저장을 한다. 왜? 메모리에 한번 털렸으니까..

그 다음은 똑같다. 일반적인 DFS로 해결해준다.

 

단, 2차원 배열이 아닌 LinkedList이기때문에 for문보단 forEach문을 사용해서 해결해준다.

물론 for(i in graph[now]) 와 같은 방식으로 해결해도 된다.

여튼 핵심은 정적인 숫자가 아닌, 동적인 방법으로 해야한다는 것이다.

 

그렇게 DFS를 돌리다보면 parent값을 발견하게 되고, 이 값을 저장하는 배열에 저장해서 배열속 값을 출력해주면 된다.

 

 

 

 

생각보다 쉬우면서도 생각할게 많았다.

그리고 LinkedList를 사용해서 DFS를 돌린다는 발상은 상당히 신선했던 것 같다. 

효율적이고 새로운 방법을 알아간다. 역시 배우는 부분은 백준 난이도에 상관 없는 것 같다.

골드 문제를 풀면서도 생각 못했던 것을 실버 문제를 풀면서 깨닫게 되는게 참 재밌으면서 신기하다.