백준 16928번 뱀과 사다리 게임

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;

public class SnakeAndLadder {
    static int N;
    static int M;
    static boolean[] visited;
    static List<int[]> ladder = new ArrayList<>();
    static List<int[]> snake = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visited = new boolean[101];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            ladder.add(new int[] {start,end});
        }
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            snake.add(new int[]{start,end});
        }
        bfs(1,0);
    }
    public static void bfs(int now,int count){
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[] {now,count});
        while (!que.isEmpty()){
            int[] current = que.poll();
            int place = current[0];
            int cnt = current[1];
            if(place==100){
                System.out.println(cnt);
                return;
            }
            for (int i = 1; i <= 6; i++) {
                int next = place+ i;
                if(next>100) continue;
                for (int j = 0; j < ladder.size(); j++) {
                    if(next==ladder.get(j)[0]){
                        next = ladder.get(j)[1];
                        break;
                    }
                }
                for (int j = 0; j < snake.size(); j++) {
                    if(next==snake.get(j)[0]){
                        next = snake.get(j)[1];
                        break;
                    }
                }

                if(!visited[next]){
                    que.add(new int[]{next,cnt+1});
                    visited[next] = true;
                }

            }
        }
    }
}

풀이방법

1. 사다리와 뱀리스트를 만들어 입력받은 값을 넣어준다.
2. bfs탐색시 다음 위치로 가능한 수는 현재 위치 + 주사위 1~6까지 수이다.
3. 이때 다음 위치에 해당하는 수가 사다리나 뱀 리스트에 있는 수라면, 추가적으로 이동한다.
   👉뱀을 거치는게 최소일 수도 있으므로, 뱀을 아예 제외하고 생각하면 안된다.
4. 방문체크를 하며 6개의 다음 위치와, 주사위 횟수를 큐에 넣어준다.
5. 위치가 100이 되면, 주사위 횟수를 출력해준다.