백준 20007 - 떡 돌리기

문제

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

리뷰

다익스트라를 통해 풀이할 수 있는 문제였다.

각 집까지의 최단 거리는 다익스트라를 통해 도출할 수 있고, 유의할 점은
거리가 가까운 집부터 방문을 해주어야 하기 때문에 dist 배열을 한 번 정렬하여
일 수(day)를 계산해주어야 한다는 부분이었다. 이 부분을 간과하여 몇 차례의
오답을 마주했다. 한편, 하루 내에 방문할 수 없는 집의 존재 여부의 경우 dist를
정렬한 후에 가장 거리가 먼 집(dist[N-1])을 기준으로 판단할 수 있다.

로직의 시간 복잡도는 다익스트라의 $O(MlogN)$으로 수렴하고 이는 $N=1,000$,
$M=100,000$인 최악의 경우에도 무난히 제한 조건 1초를 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static long[] dist;
    static List<List<Node>> graph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = parseInt(st.nextToken());
        dist = new long[N];
        for (int i = 0; i < N; i++) graph.add(new ArrayList<>());

        int M = parseInt(st.nextToken());
        int X = parseInt(st.nextToken());
        int Y = parseInt(st.nextToken());

        int u, v;
        long w;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            u = parseInt(st.nextToken());
            v = parseInt(st.nextToken());
            w = Long.parseLong(st.nextToken());

            graph.get(u).add(new Node(v, w));
            graph.get(v).add(new Node(u, w));
        }

        dijkstra(Y);
        int day = 1;
        long sum = 0;

        Arrays.sort(dist);
        if (dist[N - 1] * 2 > X) {
            System.out.println(-1);
            return;
        }

        for (long d : dist) {
            if (sum + 2 * d <= X) {
                sum += 2 * d;
            } else {
                day++;
                sum = 2 * d;
            }
        }

        System.out.println(day);
        br.close();
    }

    static void dijkstra(int Y) {
        Arrays.fill(dist, Long.MAX_VALUE);
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingLong(n -> n.w));
        dist[Y] = 0;
        pq.offer(new Node(Y, dist[Y]));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (dist[cur.u] < cur.w) continue;

            for (Node next : graph.get(cur.u)) {
                if (dist[next.u] < dist[cur.u] + next.w) continue;

                dist[next.u] = dist[cur.u] + next.w;
                pq.offer(new Node(next.u, dist[next.u]));
            }
        }
    }

    static class Node {
        int u;
        long w;

        public Node(int u, long w) {
            this.u = u;
            this.w = w;
        }
    }
}

결과