[백준] 16928번 - 뱀과 사다리 게임 (Gold 5)

문제 링크

백준 16928번 - 뱀과 사다리 게임 (Gold 3)

문제 설명

주어진 뱀과 사다리 게임이 있을 때, 1에서 100까지 가장 빠르게 도달하는 경우를 구한다.

정답 코드 및 설명

뱀과 사다리는 사실 구분할 필요가 없다.
둘 다 시작점에서 끝점으로 강제로 이동시키므로, 그냥 시작점과 끝점을 같은 점으로 취급하면 된다.
최단 경로의 길이를 구하는 문제로 취급할 수 있으므로, BFS를 사용한다.

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

public class Main {

    static HashMap<Integer, Integer> map = new HashMap<>();
    static int[] dist = new int[101];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        // 사다리와 뱀 저장
        for (int i = 0; i < n + m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            map.put(v1, v2);
        }
        bw.write(min() + "");
        bw.close();
    }

    // BFS로 탐색
    static int min() {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        dist[1] = 1;
        while (!queue.isEmpty()) {
            int start = queue.poll();
            for (int i = 1; i <= 6; i++) {
                int end = start + i;
                if (end <= 100 && dist[end] == 0) {
                    // 도착점에서부터 시작되는 사다리 또는 뱀이 있는 경우
                    // 도착점을 사디리 또는 뱀 탄 지점으로 바꿔버림
                    if (map.get(end) != null)
                        end = map.get(end);
                    queue.add(end);
                    if (dist[end] == 0 || dist[start] < dist[end])
                        dist[end] = dist[start] + 1;
                    if (dist[100] != 0)
                        return dist[100] - 1;
                }
            }
        }
        return -1;
    }
}