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

-Code

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

public class BOJ16928 {
    static boolean[] visited = new boolean[101];
    static int[] gameMap = new int[101];

    public static void main(String[] args) throws Exception {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        //좌표에 도착하면 이동하는 곳을 map으로 저장
        Map<Integer, Integer> ladderAndSnakeMap = new HashMap<>();
        for (int i = 0; i < n + m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            ladderAndSnakeMap.put(start, end);
        }
        // bfs
        minRollDice(1, ladderAndSnakeMap);
        // 출력
        System.out.println(gameMap[100]);
    }

    private static void minRollDice(int start, Map<Integer, Integer> ladderAndSnakeMap) {
        // 시작점 방문 및 덱 셋팅
        visited[start] = true;
        Deque<Integer> posDeque = new ArrayDeque<>();
        posDeque.addLast(start);
        // 덱을 통해 반복
        while (!posDeque.isEmpty()) {
            int nowPos = posDeque.pollFirst();
            // 100에 도착하면 그만 검사
            if (nowPos == 100) {
                return;
            }
            // 주사위를 통해 이동하므로 1 ~ 6 이동해보며 탐색
            for (int i = 1; i <= 6; i++) {
                int nextPos = nowPos + i;
                if (!isMove(nextPos)) continue;
                // 사다리나 뱀을 만나면 다음 위치 변수를 그에 해당하는 다음 위치로 변경
                if (ladderAndSnakeMap.containsKey(nextPos)) {
                    nextPos = ladderAndSnakeMap.get(nextPos);
                }
                // 뱀이나 사다리를 타고난 다음 위치로 계산후 방문 체크
                if (!visited[nextPos]) {
                    visited[nextPos] = true;
                    // 현재 위치의 +1하고 다음 위치에 저장
                    gameMap[nextPos] = gameMap[nowPos] + 1;
                    // 다음에 탐색할 위치에 추가
                    posDeque.addLast(nextPos);
                }
            }
        }
    }
    // 범위 탐색
    private static boolean isMove(int pos) {
        return 0 < pos && pos <= 100;
    }
}

이 문제의 로직을 처음 짰을 때 아래와 같이 일반적인 bfs에서 조금 비틀어서 이동 위치가 범위 안이고 방문하지 않았을 경우 다음 로직인 뱀이나 사다리가 있을 때 위치 교정이었습니다.                      

if (isMove(nextPos) && !visited[nextPos]) {
    // 사다리나 뱀을 만나면 그에 해당하는 위치로 이동
    if (ladderAndSnakeMap.containsKey(nextPos)) {
        nextPos = ladderAndSnakeMap.get(nextPos);
        visited[nextPos] = true;
    }
    // 현재 위치의 +1하고 다음 위치에 저장
    gameMap[nextPos] = gameMap[nowPos] + 1;
    // 다음에 탐색할 위치에 추가
    posDeque.addLast(nextPos);
}

하지만 이렇게 하면 다음과 같은 문제가 발생했습니다.

1. 워프가 만약 다음과 같이 이어진 경우(2 -> 20, 20 -> 50), 2의 위치가 되면 visited[20]을 true로 gameMap[20]을 1로 변경 후 20을 Duque에 저장
2. Deque에 서 들어온 20을 통해 다음 워프인 50으로 가야 하는데 visited[20]이 true여서 다음 워프 지점인 50으로 최단 거리를 갈 수가 없습니다.

그래서 처음 틀렸을 때 뭐가 문제인지 몰라 찾아보고 해 보니 범위는 당연히 벗어나면 안 되니 미리 검사를 하고 그 뒤에 Map으로 저장한 KeySet 중에 일치하면 다음 위치로 이동 킨 후에 방문 여부를 통한 검사를 하도록 if문의 visited 검사 위치를 변경시켜 해결했습니다.