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

16928번: 뱀과 사다리 게임

---

[Dijkstra]

BFS로 풀어보았으나 풀다보니 다익스트라 알고리즘이 더 풀기 쉬울 것 같아서 급히 방향을 바꾸어서 풀었다.

 

map[ ]이라는 배열을 만들어서 i번 째 원소의 값은 i로 초기화한다. 그리고 n, m만큼 뱀과 사다리의 정보를 받아 해당 map[ i ]의 값을 바꾸고 다익스트라 알고리즘을 수행하면 된다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point{
        int x, m;
        public Point(int xx, int move){
            x=xx;
            m=move;
        }
    }
    static final int INF = 1000000000;
    static int[] map = new int[101], move = new int[101];

    static int Dijkstra(){
        Queue<Point> Q = new PriorityQueue<>((a, b) -> a.m - b.m);

        move[1] = 0;
        Q.add(new Point(1, 0));

        while(!Q.isEmpty()){
            Point p = Q.poll();
            int cur = p.x;
            int m = p.m;

            if(move[cur] < m) continue;

            for(int i=1; i<7; i++){
                int next = cur + i;

                if(next > 100) continue;

                if(move[ map[next] ] > m+1) {
                    move[map[next]] = move[cur] + 1;
                    Q.add(new Point(map[next], m + 1));
                }
            }
        }
        return move[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());

        for(int i=1; i<=100; i++) {
            map[i] = i;
            move[i] = INF;
        }

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());

            int target = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());

            map[target] = dest;
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int target = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());

            map[target] = dest;
        }

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