백준 2644 Kotlin : 촌수계산

백준 2644: 촌수계산 풀이

그래프 유형 문제에 진짜 뒤지게 약하다.
그래서 지금 부터 당분간 그래프 유형의 문제만 파볼 예정이다

보통 내가 그래프 문제를 마주하면 당황하는 이유가 어떤 자료구조를 적용해야 하는지를 파악을 잘 못하는 데에 있는 것 같다.

딱 정리해둔다.

모든 가능한 경우의 수를 탐색하는 문제: DFS
최단 경로를 찾는 문제: BFS

이 문제도 처음에 BFS로 풀다가 DFS로 풀이 방법을 변경했다.

풀이 코드

fun main() {
    val n = readln().toInt()
    val (x, y) = readln().split(" ").map { it.toInt() }
    val m = readln().toInt()

    val arr = List(n) { MutableList(n) { 0 } }

    val visited = MutableList(n) { false }
    repeat(m) {
        val (a, b) = readln().split(" ").map { it.toInt() - 1 }
        arr[a][b] = 1
        arr[b][a] = 1
    }

    var result = -1

    fun dfs(index: Int, cnt: Int) {
        if (visited[index]) return
        visited[index] = true
        if (index == y - 1) {
            result = cnt
            return
        }
        for (i in 0 until n) {
            if (arr[index][i] == 1 && !visited[i]) {
                dfs(i, cnt + 1)
            }
        }
    }
    
    dfs(x - 1, 0)
    println(result)
}

여기서 dfs에 cnt를 인자로 계속 넘겨주면 되는걸 외부 변수로 해결해 보겠다고 설치다가 시간을 좀 더 잡아먹어버렸다