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

생각 정리

bfs 탐색은 일반적으로 1,2,3,4,5,6 칸을 한다.
다만, 숫자가 100을 넘어가거나 방문을 했다면 skip
100에 도착했을 떄, 주사위 굴렸던 횟수를 출력한다. (100에 도착하지 못하는 경우는 없다고 한다)

이정도 ..?

생각하지 못한 것

뱀이나 사다리라면 해당 칸이 아니고 '해당 칸을 통해 이동되는 칸' 에 대해서 큐에 넣고 방문표시를 한다.

10x10이라고 해서, 숫자를 다시 이차원배열로 넣고 다시 숫자로 만드는 복잡한 과정을 거쳤는데, 검색해보니 그냥 일차원배열로 하는게 훠어얼씬 편해보였다.

코드

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

public class Main {
    static int[] board = new int[101];
    static int[] visited = new int[101];
    static int N, M;

    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()); //뱀의 수

        Arrays.fill(visited, -1);

        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());

            board[start] = end;
        }

        bfs(1);
        //System.out.println(min);
    }

    static void bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();
        int[] dx = {1, 2, 3, 4, 5, 6};
        queue.add(n);
        visited[n] = 0;

        while(!queue.isEmpty()) {
            int out = queue.poll();

            if(out == 100){
                System.out.println(visited[out]);
                return ;
            }

            
            //System.out.println(ox + " , " + oy + " -> " + out +  " / " +  (visited[ox][oy] + 1));
            for(int i=0; i<6; i++) {
                int nx = out+ dx[i];

                if(nx < 0 || nx > 100) continue;
                if(visited[nx] > -1 ) continue;
                if(board[nx] != 0) { //뱀이나 사다리인 경우
                    int num = board[nx];

                    if(visited[num] == -1) { //뱀이나 사다리로 이동하는 곳을 아직 방문하지 않았다면, 그곳을 큐에 넣는다.
                        queue.add(num);
                        visited[num] = visited[out] + 1;
                    }
                }
                //그냥 주사위 굴리는 중 
                else {
                    queue.add(nx);
                    visited[nx] = visited[out] + 1;
                }

            }
        }

    }
    
}