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

내 풀이

100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해야했으므로, 최단경로를 구할 수 있는 BFS 알고리즘을 떠올렸다.

먼저, 10*10칸이라고 하길래 board의 2중 배열 형태를 생각하였지만, 이중배열로는 잘 구현이 되지 않았고 뱀과 사다리가 있는 칸 마다 이동하는 데 많은 고민이 필요했다.

결국 현재 위치에서 앞 뒤로 +나 -연산만 필요하므로, board를 1차원 배열로 1부터 100까지 쭉 늘어트린 형태로 수정하여 구현하였다.

풀이과정은 다음과 같다.

1. board 배열의 각 칸은 다음으로 이동해야할 칸의 번호를 저장
2. bfs 탐색
   a. 큐에 현재 위치과 주사위를 굴릴 횟수 저장
   b. 주사위로 나올 수 있는 이동할 수 있는 모든 칸 수 탐색
   c. 100번째 칸에 도착하면 종료
3. 횟수 출력

코드

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

public class Main {
    static int[] board;
    static boolean[] visited;
    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());

        board = new int[101];
        visited = new boolean[101];

        for (int i = 1; i <= 100; i++) {
            board[i] = i;
        }

        // 사다리
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            board[x] = y;
        }

        // 뱀
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            board[u] = v;
        }

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

    static int bfs() {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {1, 0});
        visited[1] = true;

        while (!queue.isEmpty()) {
            int[] xy = queue.poll();

            for (int i = 1; i <= 6; i++) {
                int nXY = xy[0] + i;

                if (nXY > 100) continue;

                if (board[nXY] == 100) return xy[1] + 1;

                if (!visited[board[nXY]]) {
                    visited[board[nXY]] = true;
                    queue.offer(new int[] {board[nXY], xy[1] + 1});
                }
            }
        }
        return -1;
    }
}