<BOJ> 11779 자바 (최소비용 구하기2)

 

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

 

23% 시간초과로 어리둥절했던 문제이다.

분명 다익스트라로 잘 구현했는데 시간초과가 발생했다.

 

문제는 아래 핵심이라고 주석메모를 해놓은 부분이다.

 

다익스트라를 구현 할 때 가중치가 작은 순으로 PQ에 담기는데,

큐에서 꺼낸 노드의 누적 비용(cur.w)이 해당 노드의 dist[cur.v]와 다를 수 있는 경우가 발생한다는 것이다.

언제? 간선의 수(m)가 많아질수록, 즉 복잡한 그래프일수록 발생할 가능성이 높아진다.

 

간선의 수가 적을 때만 테스트 해보니 간과했던 부분이었다.

 

왜 이런 상황이 발생하는지 설명하겠습니다:

1. PriorityQueue 특성: 다익스트라 알고리즘에서 우선순위 큐는 가장 짧은 거리를 가진 노드를 먼저 꺼냅니다. 하지만 큐에 이미 다른 경로를 통해 해당 노드를 여러 번 삽입할 수 있습니다. 즉, 어떤 노드를 큐에 넣고 나서 더 짧은 경로를 찾게 되면 그 노드는 다시 큐에 들어가게 됩니다.
2. 경로 갱신: 노드를 처음 방문할 때는 그 노드까지의 최단 거리를 모르는 경우가 많습니다. 이후 다른 경로를 통해 더 짧은 거리가 갱신되면 다시 큐에 들어가서 처리해야 합니다. 하지만 그보다 더 긴 경로로도 큐에 들어갈 수 있습니다. 즉, 큐에 들어간 노드가 이미 최단 거리로 갱신된 후, 다시 큐에서 꺼내지게 되는 상황이 발생할 수 있습니다.
3. 큐에 중복으로 노드가 들어가는 상황:
   • 한 노드까지 도달하는 경로가 여러 개 존재할 때, 이 경로들의 길이가 다를 수 있습니다.
   • 예를 들어, 노드 A에 도달하는 두 경로가 각각 길이 5와 길이 10일 수 있습니다. 처음 길이 10짜리 경로가 큐에 들어갔고, 이후에 길이 5짜리 경로로 갱신되었다면, 두 경로 모두 큐에 들어가게 됩니다. 이때 길이 10인 경로로 큐에서 꺼낸 후에는 dist[A]가 이미 더 작은 값으로 갱신되어 있을 수 있습니다.
4. 결과적으로 발생하는 문제: 이러한 이유로 큐에서 꺼낸 노드의 누적 비용(cur.w)이 그 노드의 dist[cur.v]보다 클 수 있습니다. 이는 이미 더 짧은 경로로 갱신되었으므로 불필요한 계산을 하게 되는 상황을 만들 수 있습니다. 이러한 상황을 방지하기 위해 if (cur.w > dist[cur.v]) 조건을 추가해 불필요한 연산을 피할 수 있습니다.

예시 상황:

• 한 노드에 대해 두 경로가 존재할 때, 먼저 긴 경로(비용이 큰 경로)가 큐에 들어갔다고 가정해봅시다.
• 이후 더 짧은 경로가 발견되어 큐에 추가됩니다.
• 이때 큐에서 꺼낸 첫 번째 노드는 긴 경로에 해당하는 값일 수 있고, 이 노드는 이미 더 짧은 경로로 갱신되었으므로 처리할 필요가 없습니다.

결론:

간선 수(m)가 많아지고, 경로의 복잡도가 증가할수록 이런 경우가 자주 발생하게 됩니다. 이 조건을 추가하지 않으면 불필요하게 중복된 노드가 큐에서 처리되며 시간 초과로 이어질 가능성이 커집니다.

 

추가로, '최소비용구하기1' 과 다른 부분은 종료 노드까지 최소비용으로 가는 route와 몇개의 노드를 거쳐가는지도 추가로 구해야 한다는 점이다.

이는 조건에 부합하여 q에 추가해줄 때 route[next노드]에 현재 노드를 입력해주면 된다.

예시 문제의 경우 이런식으로 배열이 완성될텐데,

1	2	3	4	5
0	1	1	1	3

 

이를 종료노드부터 원소들을 리스트에 차곡차곡 담은 뒤 역순으로 StringBuilder에 담아 출력해주면 된다.

 

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

public class b11779_최소비용구하기2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        List<Edge>[] list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            list[s].add(new Edge(e, w));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());

        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        PriorityQueue<Edge> q = new PriorityQueue<Edge>();
        q.offer(new Edge(s, 0));
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[s] = 0;
        int[] route = new int[n + 1];

        while (!q.isEmpty()) {
            Edge cur = q.poll();
            if (cur.w > dist[cur.v]) {
                continue;    // 핵심!
            }
            for (Edge next : list[cur.v]) {
                if (dist[cur.v] + next.w < dist[next.v]) {
                    dist[next.v] = dist[cur.v] + next.w;
                    route[next.v] = cur.v;
                    q.offer(new Edge(next.v, dist[next.v]));
                }
            }
        }
        int d = e;
        int cnt = 1;
        List<Integer> ans = new ArrayList<>();
        ans.add(e);
        while(d!=s) {
            ans.add(route[d]);
            d = route[d];
            cnt++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = ans.size()-1; i >= 0; i--) {
            sb.append(ans.get(i)).append(" ");
        }
        System.out.println(dist[e]);
        System.out.println(cnt);
        System.out.println(sb);
    }

    private static class Edge implements Comparable<Edge> {

        int v;
        int w;

        public Edge(int v, int w) {
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Edge o) {
            return this.w - o.w;
        }
    }
}