P.14938 서강그라운드

코드

package Baekjoon.Class;

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

public class P_14938 {

    static int n;
    static PriorityQueue<Node>[] graph;
    static int[] items;
    static int ans = 0;

    static class Node {
        int edge;
        int weigh;

        public Node(int edge, int weigh) {
            this.edge = edge;
            this.weigh = weigh;
        }
    }

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

        int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        n = line[0]; int m = line[1], r = line[2];
        items = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        graph = new PriorityQueue[n + 1];
        for (int i = 0; i <= n; i++) graph[i] = new PriorityQueue<>(Comparator.comparing(o -> o.weigh));
        for (int i = 0; i < r; i++) {
            line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            graph[line[0]].add(new Node(line[1], line[2]));
            graph[line[1]].add(new Node(line[0], line[2]));
        }

        for (int i = 1; i <= n; i++) {
            int[] distance = new int[n + 1];
            Arrays.fill(distance, Integer.MAX_VALUE);
            distance[i] = 0;
            dijkstra(i, distance);
            calc(distance, m);
        }

        bw.write(Integer.toString(ans));
        bw.flush();
    }

    private static void calc(int[] distance, int m) {
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (distance[i] <= m) cnt += items[i - 1];
        }

        ans = Math.max(ans, cnt);
    }

    private static void dijkstra(int cur, int[] distance) {
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparing(o -> o.weigh));
        queue.add(new Node(cur, 0));

        while (!queue.isEmpty()) {
            Node poll = queue.poll();

            for (Node node : graph[poll.edge]) {
                if (distance[node.edge] > poll.weigh + node.weigh) {
                    distance[node.edge] = poll.weigh + node.weigh;
                    queue.add(new Node(node.edge, poll.weigh + node.weigh));
                }
            }
        }
    }
}

코드 설명

한 정점에서 임의의 정점까지의 모든 거리를 구하는 다익스트라 알고리즘을 이용하는 문제이다.

1번 정점에서 출발할 때 부터 n번 정점에서 출발할 때의 모든 각각의 거리를 구해야하므로 n번의 다익스트라 알고리즘을 이용한다.

 

다익스트라 알고리즘에서 visited 배열을 사용해서 몇 번 틀렸다.

visited를 사용할 경우 아무리 priorityQueue를 사용한다고 하더라도 이후에 등장하는 weigh의 합이 작을 때에 업데이트를 해줄 수 없으므로 틀린 답을 구하게 된다.

1에서 출발한다고 가정하였을 때, 다음 예시를 보자.
1 2 5
1 3 2
2 4 10
3 4 12

1. queue에 1이 삽입되며 (1 -> 3), (1 -> 2) 노드가 차례대로 queue에 등록된다.
2. queue에서 (1 -> 3)이 제거되며 (3 -> 4)번 노드가 queue에 등록된다. 이 때 순서는 (1 -> 2) -> (3 -> 4)이다.
3. queue에서 (1 -> 2)가 제거되며 (2 -> 4)번 노드가 queue에 등록된다. 이 때 순서를 (2 -> 4) -> (3 -> 4)이다.
4. queue에서 (2 -> 4)가 제거되며 이 때 4번 노드로 가는 distance는 15이다.
5. queue에서 (3 -> 4)가 제거되고 4번 노드로 가는 distance는 14로 15보다 최솟값이지만 이미 distance[4]가 방문이 되었기 때문에 업데이트 할 수 없다.

 

이 문제를 피하기 위해 visited를 제거하면 된다.

visted를 제거할 경우 priorityQueue를 사용한다고 하더라도 막을 수 없는 삽입 순서로 인한 오답을 막을 수 있다.