[백준/코틀린] 12851번: 숨바꼭질 2

링크

12851번: 숨바꼭질 2

풀이

일반적인 BFS에서는 visited를 큐에 넣는(enqueue) 시점에 체크하여,
각 정점에 최초 1회만 도달하도록 합니다.
하지만 이 문제에서는 같은 정점에 같은 뎁스로 도달하는 모든 경우를 세야 하므로,
visited를 큐에서 꺼내는(dequeue) 시점에 체크합니다.

이렇게 하면 같은 BFS 뎁스에 있는 여러 정점이 동일한 다음 정점을 큐에 넣을 수 있어,
최단 경로의 가짓수를 구할 수 있습니다.

BFS 큐에는 현재 뎁스와 다음 뎁스(+1)가 함께 존재할 수 있으므로,
min < depth 검사가 없다면 최단 시간보다 1 깊은 경로까지 카운트하게 됩니다.

코드

const val MAX = 100001
val visited = BooleanArray(MAX)
val mul = listOf(1, 1, 2)
val add = listOf(-1, 1, 0)
var min = Int.MAX_VALUE
var minCnt = 0

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

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

        if (current == target) {
            if (min < depth) break

            min = depth
            minCnt++
            continue
        }
        repeat(3) {
            val next = mul[it] * current + add[it]

            if (next in 0 until MAX && !visited[next]) {
                queue.addLast(next to depth + 1)
            }
        }
    }
}

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

    bfs(n, k)

    println(min)
    println(minCnt)
}

연관 문제

• [백준/코틀린] 1697번: 숨바꼭질 - 최단 시간만 구하는 기본 BFS
• [백준/코틀린] 13549번: 숨바꼭질 3 - 순간이동 비용이 0인 0-1 BFS