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

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

16928번: 뱀과 사다리 게임

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] dice = {1, 2, 3, 4, 5, 6};
    static int[] snakeLadder = new int[101];
    static int[] minCnt = new int[101];
    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()) + Integer.parseInt(st.nextToken());
        Arrays.fill(minCnt, Integer.MAX_VALUE);
        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            snakeLadder[Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
        }
        bfs(1);
        System.out.println(minCnt[100]);
    }

    private static void bfs(int start) {
        Queue<Root> queue = new LinkedList<>();
        queue.add(new Root(start, 0));
        minCnt[start] = 0;
        while (!queue.isEmpty()) {
            Root now = queue.poll();
            for (int d : dice) {
                int nextPos = now.pos + d;
                if(nextPos > 100) break;
                nextPos = snakeLadder[nextPos] == 0 ? nextPos : snakeLadder[nextPos];
                if (minCnt[nextPos] > now.diceCnt + 1) {
                    queue.add(new Root(nextPos, now.diceCnt + 1));
                    minCnt[nextPos] = now.diceCnt + 1;
                }
            }
        }
    }
    private static class Root {
        int pos; int diceCnt;

        Root(int pos, int diceCnt) {
            this.pos = pos;
            this.diceCnt = diceCnt;
        }
    }
}

💡 BFS

풀이

• 사다리, 뱀 정보를 배열에 한꺼번에 저장함
  • "모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있으며, 동시에 두 가지를 모두 가지고 있는 경우는 없다"
• 주사위 값을 더한 좌표로 검사
  • 1) 100을 넘는지 (넘으면 해당 for문 빠져 나옴. 더 큰 눈들은 당연히 100 넘으므로
  • 2) 이동한 좌표에 사다리 or 뱀이 있는지 - 있다면 연결된 좌표로 값 갱신
  • 3) 불필요한 탐색을 차단하기 위해, 새로운 좌표로 가는 최단 경로가 아닐 경우 해당 경우는 큐에 넣지 않음