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

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

16928번: 뱀과 사다리 게임

문제 풀이

1. 사다리의 정보와 뱀의 정보를 Int배열에 저장한다. 사다리와 뱀의 정보가 서로 다른 위치의 값이므로 하나의 Int배열에 저장해도 무방하다.

2. 사다리의 x, 뱀의 u 를 index 로 하고 y, v를 value 하여 배열에 저장한다.

3. 1번째부터 시작하여 BFS 를 이용하여 탐색한다.

4. 현재 위치가 100이면 결과를 출력한다.

5. 다음 탐색할 위치가 1 보다 작고 100보다 크면 범위를 벗어 났으므로 다음 탐색을 한다.

6. 사다리나 뱀의 위치에 해당 될 경우 해당되는 위치를 배열 값을 다음 위치로 Queue 에 저장한다.

코드

import java.io.*
import java.util.*

private var result = Int.MAX_VALUE

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val ladder = IntArray(101) { 0 }
    val snake = IntArray(101) { 0 }

    // 사다리 정보 저장
    repeat(N) {
        val (x, y) = br.readLine().split(" ").map { it.toInt() }
        ladder[x] = y
    }

    // 뱀 정보 저장
    repeat(M) {
        val (u, v) = br.readLine().split(" ").map { it.toInt() }
        snake[u] = v
    }

    bfs(ladder, snake)
    println(result)
}

private fun bfs(ladder: IntArray, snake: IntArray) {
    val queue = LinkedList<Pair<Int, Int>>() // 0: 현재 위치, 1: 주사위 굴린 횟수
    queue.add(Pair(1, 0))
    val visit = BooleanArray(101) { false }
    // 첫번째 위치는 방문했으므로 true 설정한다.
    visit[1] = true

    while (queue.isNotEmpty()) {
        val (cPos, cCount) = queue.pop()
        //println("current $cPos, $cCount")

        if (cPos == 100) {
            result = Math.min(result, cCount)
        } else {
            for (i in 1..6) {
                val nPos = cPos + i

                if (nPos < 1 || nPos > 100) continue

                // 이미 방문한 위치이므로 다음 탐색을 한다.
                if (visit[nPos]) continue

                if (ladder[nPos] != 0) {
                    visit[nPos] = true
                    visit[ladder[nPos]] = true
                    queue.add(Pair(ladder[nPos], cCount + 1))
                } else if (snake[nPos] != 0) {
                    visit[nPos] = true
                    visit[snake[nPos]] = true
                    queue.add(Pair(snake[nPos], cCount + 1))
                } else {
                    visit[nPos] = true
                    queue.add(Pair(nPos, cCount + 1))
                }
            }
        }
    }
}