[Kotlin, G5] 백준 16928번 뱀과 사다리 게임

출처: unsplash.com

 

뱀과 사다리 게임(16928번)

Gold 5

#그래프 이론 #그래프 탐색 #너비 우선 탐색

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

 

문제 내용

 

 

문제 접근

1부터 100번째 칸까지 존재하는 뱀과 사다리 게임판이 존재할 때, n개의 사다리와 m개의 뱀이 있다.

사다리를 밟으면 위로 이동하고 뱀을 밟으면 아래로 내려간다.

입력 예제 1을 예로 들면

3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

사다리가 3개, 뱀이 7개 있고 2번째 줄부터 순서대로 사다리, 뱀을 입력받는다.

숫자 2개가 있는데, 사다리 32 62를 예로 들면 32를 밟게 되면 62로 이동하고, 4번째 줄인 뱀 95 13의 경우는 95를 밟으면 13으로 내려간다.

 

주사위를 적게 돌리면서 말을 100까지 옮겨야 한다. 입력 예제 1의 정답은 3이다.

1에서 시작해 6으로 돌려 7로 이동하고 5를 돌려 12로 이동하면 98로 사다리를 타고 이동한다. 2를 돌리면 100에 도달한다.

1 -> 7 -> 98 -> 100의 순서로 주사위를 3번 돌리면 100에 도달한다.

 

주사위를 굴리는 최솟값을 구하기 위해서는 1부터 6까지 주사위를 돌리는 경우를 모두 확인해서 가장 먼저 100에 도달하는 경우가 제일 빠른(최솟값) 경우가 될 것이다.

현재 위치는 처음에는 1로 설정한다.

이제 1에서 1부터 6까지 주사위를 돌려 가면서 움직인 값에 뱀 또는 사다리가 있는지 확인한다. 만약 뱀 또는 사다리가 있으면 맞게 말을 추가로 이동한다.

이동이 완료되면 방문 표시를 한다. 다시 그 땅을 다시 밟게 되었을 때는 처음에 밟았던 경우보다 더 주사위를 굴려야 하는 경우이기 때문이다.

 

프로세스 과정을 간단하게 표로 구성해 보았다.

초기 1은 주사위를 0번 굴리기 때문에 move가 0이다. 1에서 주사위를 1부터 6을 굴리는 결과가 2, 3, 4, 5, 6, 7에는 move를 1로 설정한다. 똑같이 8, 9, 10, 11, 12, 13에도 이전과 같이 move를 2로 설정한다.

12번째 칸에 98로 향하는 사다리가 있으므로 98로 이동한다. 주사위를 굴리지 않고 98로 이동했기 때문에 move는 변하지 않는다.

이제 98에서 99, 100을 주사위를 1번 더 굴려서(move: 3) 만들 수 있다. 100에 도달했으므로 3을 출력한다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

private val ladderSnake = mutableMapOf<Int, Int>()
private val visited = BooleanArray(101)
private var result = 0

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (ladder, snake) = readLine().split(" ").map { it.toInt() }

    for (i in 1 .. ladder) {
        val (ladderStart, ladderEnd) = readLine().split(" ").map { it.toInt() }
        ladderSnake[ladderStart] = ladderEnd
    }

    for (i in 1 .. snake) {
        val (snakeStart, snakeEnd) = readLine().split(" ").map { it.toInt() }
        ladderSnake[snakeStart] = snakeEnd
    }

    bfs()

    println(result)
}

private fun bfs() {
    val queue = ArrayDeque<List<Int>>()
    queue.addFirst(listOf(1, 0))     // 현재 위치, 움직인 횟수
    visited[1] = true

    while (queue.isNotEmpty()) {
        val data = queue.removeLast()
        val locate = data.first()
        val move = data.last()

        if (locate >= 100) {
            result = move
            return
        }

        for (m in 1 .. 6) {
            val location = locate + m

            if (location > 100) continue
            if (visited[location]) continue

            if (ladderSnake.containsKey(location)) {
                queue.addFirst(listOf(ladderSnake[location]!!, move + 1))
                visited[ladderSnake[location]!!] = true
            } else {
                queue.addFirst(listOf(location, move + 1))
                visited[location] = true
            }
        }
    }
}

 

문제 풀이

사다리와 뱀을 저장할 map을 생성한다. key가 작동하는 칸이고, value를 이동되는 칸으로 설정한다.

visited로 방문 여부를 확인해 줘야 한다.

 

ladderSnake에 ladder와 snake를 입력받아서 저장해 준다.

그다음 bfs를 수행한다.

 

bfs에는 queue를 이용해 데이터를 저장한다.

queue를 arrayDeque를 사용해서 move가 적은 순으로 먼저 작동하도록 해준다.

arrayDeque에는 list로 입력받는데, 현재 있는 칸의 위지, 움직인 횟수를 입력받는다.

초기에는 1번째 칸에 있기 때문에, 칸을 1로, 움직인 횟수를 0으로 설정한다.

그리고 1번 visited를 체크한다.

 

queue가 빌 때까지 반복한다.

반복문에는 주사위를 1부터 6까지 돌리는 경우를 모두 확인한다.

주사위를 돌려 움직인 위치를 location에 저장하고 visited의 location번째 데이터가 이미 방문한 데이터이면 넘어간다. 또한 location이 100이 넘어가게 되면 visited를 체크하는 게 불가능하다(visited의 size가 101이다).

 

location이 ladderSnake의 시작 칸에 들어가면 value의 칸으로 이동시킨 결과를 queue에 담아 준다.

아닌 경우에는 location을 queue에 넣어 준다.

 

 

문제 해결 과정

현재 사용자의 위치를 굳이 List를 만들어 저장할 필요가 없었던 문제였다.

기존의 그래프 탐색 때는 graph List를 만들어서 사용했었는데, 이번 문제에는 만들지 않아도 된다.

queue에 현재 칸에 있는 위치를 저장해서 사용했다.

로직 구성에 대한 예외 처리 때문에 타 블로그의 해설 코드를 참고했다.