[백준] 16928 - 뱀과 사다리 게임

BFS 를 이용하여 최소한의 주사위 굴린 횟수를 출력하는 문제.
골드 1, 2였던 다른 문제보다 개인적으로 어렵게 풀었다..
뱀과 사다리가 존재하는 칸에 진입하는 경우 '무조건' 그것을 타야하는 것을 명심해야 한다.

풀이

import java.util.StringTokenizer

/*
* 1번칸에서 시작. i + 주사위 수로 이동.
* 첫 줄 - 사다리 수 N, 뱀 수 M
* 둘째 줄 ~ N개줄 - 사다리 정보 x, y
* 그 다음 M개줄 - 뱀 정보 x, y
*
* 최단 경로이므로 BFS
* */
private const val IS_NOT_VISIT = -1
private const val IS_NOT_EXIST = 0
private var board = IntArray(100 + 1){ IS_NOT_VISIT }
private var moveArr = IntArray(100 + 1)
private val arrayDeque = ArrayDeque<Int>()

fun `16928-뱀과 사다리 게임`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (ladderCount, snakeCount) = br.readLine().split(" ").map { it.toInt() }

    repeat(ladderCount){
        val token = StringTokenizer(br.readLine())
        val start = token.nextToken().toInt()
        val arrive = token.nextToken().toInt()

        moveArr[start] = arrive
    }
    repeat(snakeCount){
        val token = StringTokenizer(br.readLine())
        val start = token.nextToken().toInt()
        val arrive = token.nextToken().toInt()

        moveArr[start] = arrive
    }

    arrayDeque.addLast(1)
    board[1] = 0

    loop@while(arrayDeque.isNotEmpty()){
        val currentLocation = arrayDeque.removeFirst()

        for(i in 1 .. 6){
            var nextLocation = currentLocation + i

            if(nextLocation > 100) break

            // 이미 방문했다면 다음 순차로 넘기기
            if(board[nextLocation] != IS_NOT_VISIT) continue

            // 이동 경로가 존재하면 다음 경로를 변경
            if(moveArr[nextLocation] != IS_NOT_EXIST){
                // 코드를 더 적게 진행하기 위해 사다리, 뱀이 존재하는 곳을 방문처리
                board[nextLocation] = board[currentLocation] + 1
                nextLocation = moveArr[nextLocation]
            }

            // 다음 경로가 방문한 적이 없다면 진행
            if(board[nextLocation] == IS_NOT_VISIT){
                board[nextLocation] = board[currentLocation] + 1
                arrayDeque.addLast(nextLocation)
            }

            if(nextLocation == 100) break@loop
        }
    }

    bw.write("${board[100]}")
    bw.flush()
    bw.close()
    br.close()
}

후기

처음에는 모든 경우의 수를 찾아야하나 싶어서 DFS 로 풀었다가, "최소" 라는 단어때문에 BFS 로 선회하였다.

더 등급이 높았던 다른 문제들보다 더 어렵게 풀었고, 코드 중 어느 곳에서 문제가 있는지 AI (제미나이, 챗지피티) 한테 물어봤더니 아무리 생각해봐도 문제가 없는 곳을 알려주길래 6시간을 삽질했는데 정작 문제 있는 곳은 다른곳이었다 ㅡㅡ

문제가 있던 부분은 변경된 다음 경로에 대해 방문한 적이 있는지 없는지도 체크를 진행하고 addLast 를 해줘야했는데, 변경 이전만 체크를 했던 게 문제였다.

아까운 내 시간.. 하지만 이번 일을 계기로 AI 를 맹신하지 말자고 다시 한 번 생각하는 계기가 되었다.

....................

2일 정도가 지나서 틀린 이유가 맞나 싶어서, 다시 코드를 살펴보니 결국, 내가 틀린 것이 맞았다는 사실을 알게 되었다.

과거 코드의 경우

            if(moveArr[nextLocation] != IS_NOT_EXIST && board[moveArr[nextLocation]] == IS_NOT_VISIT){
                board[nextLocation] = board[currentLocation] + 1
                nextLocation = moveArr[nextLocation]
            }            

            if(board[nextLocation] == IS_NOT_VISIT){
                board[nextLocation] = board[currentLocation] + 1
                arrayDeque.addLast(nextLocation)
            }

로 진행했었는데, 사다리가 15 -> 30으로 간다고 치면 이 경우 주사위 3번을 굴려 [15] 에 도착 후 30으로 움직인다.

만약 이후의 주사위 굴림에서 [15] 에 도착하는 경우, VISIT 처리가 되어있기 때문에 사다리를 타지 않는다. (게임의 규칙 위반에 해당)

반면 고친 코드는 아래와 같다.

            if(moveArr[nextLocation] != IS_NOT_EXIST){
                // 코드를 더 적게 진행하기 위해 사다리, 뱀이 존재하는 곳을 방문처리
                board[nextLocation] = board[currentLocation] + 1
                nextLocation = moveArr[nextLocation]
            }

            // 다음 경로가 방문한 적이 없다면 진행
            if(board[nextLocation] == IS_NOT_VISIT){
                board[nextLocation] = board[currentLocation] + 1
                arrayDeque.addLast(nextLocation)
            }

이전에 사다리나 뱀을 탔더라도, 후순위에서 이것에 영향을 받지 않는다는 것이다.

[15] -> [30], [17] -> [99] 가 있을때

1. 주사위 3번 -> 15를 타고 30
2. 주사위 4번 -> 15 도착. 예제 1의 경우 머무르게 됨. (이 경우 다음에 17을 탈 수 있어 에러)

와 같은 상황이 발생할 수 있다.

AI 들은 이러한 상황을 방지하라는 의미였던 것 같은데, 당시의 나는 말을 이상하게 오해해서 알아듣지 못하고 시간낭비를 한 것 이었다.

오랜 시간이 걸렸지만 결국 문제의 원인을 알게 되어서 정말 다행이라고 생각한다.