문제 링크

풀이

크기가 100인 배열을 선언한 후, 각 칸에 해당하는 숫자를 저장한다.
뱀이나 사다리가 있는 경우, 해당 인덱스의 배열 값에 이동 후 도착하는 곳의 값을 저장한다.

board[16] = 41;	// 사다리가 16 -> 41 일 경우
board[1] = 1;	// 사다리, 뱀이 없는 일반 칸의 경우 

1번 칸에서 출발하여 BFS로 100번 칸까지 최단 거리로 이동한다.
큐에는 주사위를 한 번 던져 도달할 수 있는 모든 칸을 저장한다.
주사위를 던진 횟수를 계산하기 위해, while문에서는 현재 큐에 들어 있는 칸 수만큼 반복문을 돌며 한 번에 처리한다.
이렇게 한 레벨(한 번의 주사위 던짐) 처리가 끝나면 주사위 던진 횟수를 1 증가시킨다.
최종적으로 100번 칸에 도달했을 때의 던진 횟수가 정답이 된다.

코드

package BOJ;

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

public class sol16928 {
    static int n, m;
    static int[] board = new int[101];
    static int moveCount = 0;

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

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

        for (int i = 1; i <= 100; i++) {    //  뱀이나 사다리가 없는 곳은 다른 곳으로 이동하지 않으므로 자기 자신으로 초기화
            board[i] = i;
        }

        //  사다리가 있는 곳은 자기자신이 아닌 이동할 위치의 값을 넣는다.
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            board[from] = to;
        }

        //  뱀도 마찬가지
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            board[from] = to;
        }

        bfs();
        System.out.println(moveCount);
    }

    public static void bfs() {
        Queue<Integer> q = new LinkedList<>();
        boolean[] visited = new boolean[101];

        q.add(1);
        visited[1] = true;

        while (!q.isEmpty()) {
            int levelSize = q.size();   //  주사위를 한 번 던졌을 때 이동 가능한 경우의 수
            for (int i = 0; i < levelSize; i++) {
                int currPos = q.poll();
                if (currPos == 100) {   //  현재 위치가 100(마지막 칸)이라면 종료
                    return;
                }

                for (int dice = 1; dice <= 6; dice++) { //  주사위를 던져서 이동할 수 있는 만큼 반복문
                    int nextPos = currPos + dice;   //  이동할 다음 위치
                    if (nextPos > 100) {    //  다음 위치가 100을 넘어가면 이동 불가
                        continue;
                    }

                    /**
                     * 주사위를 굴려 이동한 칸(nextPos)에 뱀이나 사다리가 있으면,
                     * 해당 칸(board[nextPos])이 최종적으로 도착해야 할 위치가 된다.
                     * 따라서 실제 이동할 위치를 movePos로 갱신해준다.
                     */
                    int movePos = board[nextPos];

                    if (!visited[movePos]) {    //  다음 위치에 방문한적이 없다면
                        visited[movePos] = true;    //  방문처리
                        q.add(movePos);
                    }
                }
            }
            moveCount++;
        }
    }
}