[BaekJoon] 10776 제국 (Java)

1.  문제 링크

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

2.  문제

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int depth;
    static int islandCount;
    static int roadCount;
    static int startIsland;
    static int endIsland;
    static Map<Integer, List<Road>> roads;

    static void input() {
        Reader scanner = new Reader();

        depth = scanner.nextInt();
        islandCount = scanner.nextInt();
        roadCount = scanner.nextInt();
        roads = new HashMap<>();
        for (int island = 1; island <= islandCount; island++) {
            roads.put(island, new ArrayList<>());
        }

        for (int road = 0; road < roadCount; road++) {
            int island1 = scanner.nextInt();
            int island2 = scanner.nextInt();
            int time = scanner.nextInt();
            int depth = scanner.nextInt();

            roads.get(island1).add(new Road(island2, time, depth));
            roads.get(island2).add(new Road(island1, time, depth));
        }

        startIsland = scanner.nextInt();
        endIsland = scanner.nextInt();
    }

    /*
     * 다익스트라를 이용한 문제
     *  - 시작점 섬에서 도착점 섬까지 정해진 바닷길을 따라 이동한다
     *  - 이때 각 바닷길에서 깎아지는 뗏목 두께가 있기 때문에 모두 깎이지 않고 도착섬까지 갈 수 있는 경로로 이동한다
     *  - 다익스트라에서 최소 시간을 저장할 배열은 2차원 배열을 이용한다
     *      - 각 섬까지 이동하면서의 뗏목 두께 역시도 시간과 관련이 있기 때문에 섬과 뗏목 두께에 따라 최소 시간을 저장하는 2차원 배열을 이용한다
     *  - 두 기준을 이용하여 다익스트라를 시작섬을 기준으로 실행하고 도착섬의 모든 뗏목 두께에서 최소 시간을 출력한다
     */
    static void solution() {
        System.out.println(dijkstra(startIsland, endIsland));
    }

    static int dijkstra(int startIsland, int endIsland) {
        Queue<Road> queue = new PriorityQueue<>();
        int[][] times = new int[islandCount + 1][depth + 1];
        for (int island = 1; island <= islandCount; island++) {
            Arrays.fill(times[island], Integer.MAX_VALUE);
        }

        queue.offer(new Road(startIsland, 0, depth));
        times[startIsland][depth] = 0;

        while (!queue.isEmpty()) {
            Road cur = queue.poll();
            if (times[cur.islandNumber][cur.depth] < cur.time) {
                continue;
            }

            for (Road next : roads.get(cur.islandNumber)) {
                int nextIsland = next.islandNumber;
                int nextTime = cur.time + next.time;
                int depth = cur.depth - next.depth;

                if (depth <= 0) {
                    continue;
                }
                if (times[nextIsland][depth] > nextTime) {
                    times[nextIsland][depth] = nextTime;
                    queue.offer(new Road(nextIsland, nextTime, depth));
                }
            }
        }

        int minTime = Arrays.stream(times[endIsland]).min().getAsInt();
        return minTime == Integer.MAX_VALUE ? -1 : minTime;
    }

    static class Road implements Comparable<Road> {
        int islandNumber;
        int time;
        int depth;

        public Road(int islandNumber, int time, int depth) {
            this.islandNumber = islandNumber;
            this.time = time;
            this.depth = depth;
        }

        @Override
        public int compareTo(Road r) {
            if (time != r.time) {
                return time - r.time;
            }
            return r.depth - depth;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}