[Algorithm/Java] 백준 16928번 - 뱀과 사다리 게임 🐍🪜🎲

---

https://www.acmicpc.net/problem/16928

---

📌 문제

문제 유형

• 그래프

문제 설명

• 뱀과 사다리가 있는 1~100번 게임판에서 주사위를 굴려 가장 빨리 100번 칸에 도착하는 최소 횟수를 구하는 문제
• 사다리를 만나면 위로 올라가고, 뱀을 만나면 아래로 떨어짐

입력

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으로 이동한다는 의미이다.

다음 M개의 줄에는 뱀의 정보를 의미하는 u, v (u > v)가 주어진다. u번 칸에 도착하면, v번 칸으로 이동한다는 의미이다.

1번 칸과 100번 칸은 뱀과 사다리의 시작 또는 끝이 아니다. 모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다. 항상 100번 칸에 도착할 수 있는 입력만 주어진다.

3 7
32 62
42 68
12 98
95 13
97 25
93 37
79 27
75 19
49 47
67 17

출력

100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 출력한다.

3

🔍 문제 풀이

[Main] 함수

1. Board를 1부터 100까지 i로 초기화
2. 뱀과 사다리 칸으로 Board 대체
3. Bfs(1) 호출 (1번칸부터 시작하므로)

[Bfs 함수]

1. 큐에다가 현재 위치 넣고 현재 위치 방문처리
2. 그리고 그 큐를 꺼낸다음 주사위 굴리기
3. 즉, 다음위치 = 현재위치 + 주사위 굴린 위치
4. 100 넘으면 continue
5. 만약 방문하지 않은 칸이라면, dist 배열에 횟수 저장 후 다음 위치로 이동

📌 헷갈린 점

move = board[next]가 필요할까?

처음에는 int move = board[next];를 쓰지 않고 그냥 next를 그대로 사용했지만,
사다리나 뱀을 타는 경우 최종 도착 위치는 board[next]로 이동해야 하기 때문에,
해당 코드를 반드시 추가해줘야 정확한 경로 계산이 가능하다는 걸 알게 됨

안 쓰면 사다리나 뱀 정보를 무시하고 단순히 주사위로만 움직이게 됨

visited[] 배열만으로 충분할까?

처음엔 visited[] 하나로도 충분하다고 생각했지만,
최소 주사위 횟수를 구하려면 각 칸까지의 거리를 따로 기록해야 함

따라서,
dist[] 배열을 사용하여 각 칸에 도달했을 때의 최소 주사위 횟수(거리)를 기록하도록 함

dist[i] = dist[current] + 1; // i번 칸까지 몇 번 만에 도달했는지 기록

BFS에서 사다리로 도착한 칸은 다시 안 봐도 되는 이유

move가 이미 visited == true일 경우,
사다리 타고 도달한 칸을 탐색 못하는 게 아닐까 걱정했지만,

BFS는 먼저 도달한 경로가 항상 최단이므로 이미 방문한 칸은 다시 탐색할 필요 없다.

💻 전체 코드

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

public class Main {
    static int[] board;
    static boolean[] visited;
    static int[] dist;

    static int bfs(int start){
        Deque<Integer> dq = new ArrayDeque<>();
        dq.offer(start);
        visited[start] = true;

        while (!dq.isEmpty()){
            int current = dq.poll();
            for(int i=1; i<=6; i++){
                int next = current + i;

                if(next > 100) continue;
                int move = board[next]; // 주의

                if (!visited[move]) {
                    dq.offer(move);
                    visited[move] = true;
                    dist[move] = dist[current] + 1;
                }
            }
        }
        return dist[100];

    }

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

        int n = Integer.parseInt(st.nextToken()); // 사다리 수
        int m = Integer.parseInt(st.nextToken()); // 뱀의 수

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

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

        // board 칸 -> 사다리 칸으로 대체
        while(n -- > 0){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            board[x] = y;
        }
        while(m -- > 0){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            board[u] = v;
        }

        int result = bfs(1); // 1번칸부터 시작
        System.out.println(result);

    }
}