[백준/코틀린] 16928번: 뱀과 사다리 게임

링크

16928번: 뱀과 사다리 게임

풀이

주사위로 이동할 수 있는 모든 경우를 BFS로 탐색해
100번 칸에 도달하는 최소 이동 횟수를 구합니다.

사다리와 뱀은 해당 칸에 도착하면 즉시 다른 칸으로 이동하므로,
이를 미리 보드에 매핑해 다음 칸 계산 시 바로 적용합니다.

코드

val board = MutableList(106) { it }
val visited = BooleanArray(101)

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

    visited[1] = true
    queue.addLast(1 to 0)
    while (queue.isNotEmpty()) {
        val (cp, cd) = queue.removeFirst()

        if (cp == 100) return println(cd)

        (1..6).forEach {
            val np = board[cp + it]
            val nd = cd + 1

            if (np <= 100 && !visited[np]) {
                visited[np] = true
                queue.addLast(np to nd)
            }
        }
    }
}

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

    repeat(n + m) {
        val (a, b) = readln().split(" ").map { it.toInt() }

        board[a] = b
    }

    bfs()
}