[백준/코틀린] 13549번: 숨바꼭질 3

링크

13549번: 숨바꼭질 3

풀이

0-1 BFS를 사용하여 최단 시간을 구합니다.

BFS가 진행되는 동안에는, 정점을 포함하는 큐에 최대 두 개의 연속한 레벨만 포함될 수 있습니다.
즉, 큐의 앞부분에는 현재 레벨(depth)의 정점들이,
뒷부분에는 다음 레벨(depth + 1)의 정점들이 들어있게 됩니다.

0-1 BFS는 간선의 가중치가 0 또는 1인 그래프에서 최단 경로를 구할 수 있습니다.
가중치가 0인 경우에는 현재 레벨과 동일한 위치에 추가하고, → addFirst
가중치가 1인 경우에는 다음 레벨에 추가합니다. → addLast

이를 통해 항상 큐를 정렬된 상태로 유지할 수 있으며,
탐색이 끝났을 때의 레벨이 최단 거리가 됩니다.

[그래프] 0-1 BFS 알고리즘

코드

val visited = BooleanArray(100001)
val mul = listOf(1, 1, 2)
val add = listOf(-1, 1, 0)
val cost = listOf(1, 1, 0)

fun bfs(start: Int, target: Int) {
    val deque = ArrayDeque<Pair<Int, Int>>()

    deque.addLast(start to 0)
    while (deque.isNotEmpty()) {
        val (current, depth) = deque.removeFirst()
        visited[current] = true

        if (current == target) return println(depth)
        repeat(3) {
            val next = mul[it] * current + add[it]

            if (next in 0..100000 && !visited[next]) {
                when (cost[it]) {
                    0 -> deque.addFirst(next to depth)
                    1 -> deque.addLast(next to depth + 1)
                }
            }
        }
    }
}

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

    bfs(n, k)
}

연관 문제

• [백준/코틀린] 1697번: 숨바꼭질 - 최단 시간만 구하는 기본 BFS
• [백준/코틀린] 12851번: 숨바꼭질 2 - 최단 경로의 가짓수까지 구하는 BFS