BOJ 16928 뱀과 사다리 게임

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {

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

        /*
         * 주사위를 조작해 내가 원하는 수가 나오게 만들 수 있다면...
         * 최소 몇 번 만에 도착점에 도착?
         *
         * 1. 1~6 주사위
         * 2. 10x10 주사위 100 칸
         * 3. 1에서 100까지 수가 하나씩 순서대로 적혀져있다.
         *
         * - 주사위 굴린 결과가 100번 칸을 넘어간다면 이동 x
         * - 도착한 칸이 사다리면 사다리를 타고 위로 이동
         * - 뱀이 있는 칸데 도착하면, 뱀을 따라서 내려가야 됨
         *
         * 1. 1~100까지 간다
         * 2. 100번 칸에 도착하기 위한 최솟값은?
         *
         *  n : 사다리 수 m : 뱀의 수
         * n 개의 줄에는 사다리 x > y이동
         * m 까지는 뱀 x > y
         * */

        // dp나 다익스트라 같음
        // 기본으로 가다가...적은 cost로 다음칸에서 더 멀리 갈 수 있는 애 보기
        // x쪽에 있는 거 밟으면 확인해야함

        Deque<Integer> deque = new ArrayDeque<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Map<Integer, Integer> dist = new HashMap<>();
        Map<Integer, Integer> mapCase = new HashMap<>();

        for (int i = 0; i < m + n; i++) {
            st = new StringTokenizer(br.readLine());
            mapCase.put(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        int[] nx = {1, 2, 3, 4, 5, 6};

        deque.add(1);
        dist.put(1, 0);
        
        while (!deque.isEmpty()) {
            int now = deque.remove();

            if (now == 100) {
                break;
            }

            for (int i = 0; i < nx.length; i++) {
                int next = now + nx[i];
                if (next > 100) {
                    continue;
                }
                // 특수성이 존재하니?
                if (mapCase.containsKey(next)) {
                    next = mapCase.get(next);
                }
                if (dist.containsKey(next)) {
                    // 이미 탐색함
                    continue;
                }
                // 최대거리 구하기
                dist.put(next, dist.get(now) + 1);
                deque.add(next);
            }
        }
        System.out.println(dist.get(100));
    }
}

이 문제는 힌트를 봤따... 사실 dp와 다익스트라 중에서 고민했는데(지름길 문제랑 비슷하다고 느껴서)
그렇게 생각하니까 구현이 좀 막막하게 느껴지고 묘하게 불편하게 느껴졌다...어떻게 구현해야되지? 그냥 그런생각이 들었는데
힌트를 보니 bfs 문제였다.

이 문제가 너비 탐색인 이유는
1. 주사위 비용은 모두 1로 고정이 되어있음 -> 다익스트라 x
2. 100으로 가는 최단 거리 -> bfs 너비 탐색
3. 뱀과 사다리로인해, 사이클(그래프)과 같은 형상이 될 수 있기 때문에 dp로 풀기 어려울 것 -> dp x
4. 시간복잡도 충분 -> dp x

그래서 결론적으로 너비 우선 탐색 그래프 탐색 문제이다.

결론적으로 이 문제의 핵심은 bfs를 떠올릴 것.
그리고 내가 실수한 부분은 또 이부분이다.

 // 특수성이 존재하니?
                if (mapCase.containsKey(next)) {
                    next = mapCase.get(next);
                }
                if (dist.containsKey(next)) {
                    // 이미 탐색함
                    continue;
                }

방문 체크를 하기 전에, 뱀 또는 사다리가 있는 부분인지 확인했어야됐는데 나는 저 if문 두개의 순서를 반대로 했었다.

이 부분을 유의해야지 논리적인 오류가 나지 않는다.

그리고 이 문제는 주사위 dx = {1, 2, 3, 4, 5, 6}
이런식으로 만들어서 그래프 탐색을 해줘야 하는게 포인트다

끝.