[백준/BOJ] 16928번: 뱀과 사다리 게임

문제

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

16928번: 뱀과 사다리 게임

해설

총 100개의 칸으로 이루어진 보드판에서 주사위를 굴려 100번째 칸에 도달할 수 있는 최소 횟수를 구하는 문제이다.

문제의 조건으로 100번 칸을 넘어가면 이동할 수 없으므로, 딱 100번째 칸에 도달했을 때의 값을 구해야 한다.

우선 뱀과 사다리 각각 어떠한 칸에 놓여 어떠한 칸으로 입력되는지를 저장해놓기 위해 두 개의 Map을 선언하였다.

이제 bfs를 수행시킬 것이다. 주사위는 1 ~ 6까지의 수가 나올 수 있으므로, 1 ~ 6을 저장할 배열을 선언한다.

반복문을 통해 현재 위치에서 1 ~ 6을 더하여 간 위치가 사다리 혹은 뱀을 저장한 Map에 포함되어 있다면, 그 위치로 가준다.

이때 방문여부처리는 해주지 않는다.

뱀을 타고 내려갔을 때, 더 빠르게 도착할 수 있는 방법이 있고, 사다리를 타고 올라갔을 때 더 빨리 도달할 수도 있기 때문이다.

이게 아닌 1 ~ 6을 더해 간 칸이라면 방문여부처리를 해주면 된다.

100번째 칸에 도달했다면, 그 때의 움직인 횟수를 반환해주면 된다.

코드

import java.util.*

private val map = IntArray(101) { i -> i }
private val visited = BooleanArray(101)
private val ladder = HashMap<Int, Int>()
private val snake = HashMap<Int, Int>()
private val move = intArrayOf(1, 2, 3, 4, 5, 6)

fun main() = with(System.`in`.bufferedReader()) {
    val (ladderCnt, snakeCnt) = readLine().split(" ").map { it.toInt() }

    repeat(ladderCnt) {
        val (from, to) = readLine().split(" ").map { it.toInt() }
        ladder[from] = to
    }

    repeat(snakeCnt) {
        val (from ,to) = readLine().split(" ").map { it.toInt() }
        snake[from] = to
    }

    val ans = play()
    println(ans)
}



private fun play(): Int {
    val que: Queue<Pair<Int, Int>> = LinkedList()
    que.add(Pair(1, 0))

    while(que.isNotEmpty()) {
        val cur = que.poll()
        val curPos = cur.first
        val curMoveCnt = cur.second

        if(curPos == 100) return curMoveCnt

        for(i in 0 until 6) {
            val nextPos = curPos + move[i]

            if(nextPos > 100 || map[nextPos] < curMoveCnt + 1 || visited[nextPos]) continue

            if(ladder.contains(nextPos)) {
                que.add(Pair(ladder[nextPos]!!, curMoveCnt + 1))
            }
            else if(snake.contains(nextPos)) {
                que.add(Pair(snake[nextPos]!!, curMoveCnt + 1))
            }
            else {
                que.add(Pair(nextPos, curMoveCnt + 1))
                visited[nextPos] = true
            }

            map[nextPos] = curMoveCnt + 1
        }
    }

    return 0
}