[Gold III] 최소비용 구하기 2 - 11779

[Gold III] 최소비용 구하기 2 - 11779

문제 링크

성능 요약

메모리: 65404 KB, 시간: 620 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2024년 11월 22일 14:45:22

문제 설명

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용과 경로를 출력하여라. 항상 시작점에서 도착점으로의 경로가 존재한다.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

둘째 줄에는 그러한 최소 비용을 갖는 경로에 포함되어있는 도시의 개수를 출력한다. 출발 도시와 도착 도시도 포함한다.

셋째 줄에는 최소 비용을 갖는 경로를 방문하는 도시 순서대로 출력한다. 경로가 여러가지인 경우 아무거나 하나 출력한다.

 

 

---

1. 기존 최소비용 구하기 문제 (https://mint723dev.tistory.com/64)에서 최단거리의 탐색 경로를 추가로 구해야한다
2. 일반적인 다익스트라 알고리즘은 단순히 최단 거리만 구하지만, 해당 문제에서는 노드까지의 경로를 저장하기 위해 Node클래스를 정의하였다
   • dest: 현재 노드 번호
   • cost: 시작점에서 현재 노드까지의 비용
   • list: 현재 노드까지 도달한 경로를 저장하는 리스트 
     • addAll() 메서드를 통해 깊은 복사를 하자 (각 노드별 독립된 경로)
     • 얕은 복사를 진행하면 여러 노드가 동일한 리스트를 공유하여 경로 결과가 올바르지 않게됨
3. 다익스트라 메서드에서 노드를 최신화할 때의 조건을 추가
   
   • 현재 구현한 다익스트라 메서드는 최단거리만 최신화할 뿐 모든 탐색 경로를 탐색하고 있다  
   • 따라서 현재 노드의 최단거리가 cost와 동일할 때 노드를 최신화 하도록 조건을 추가했다

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

class Main {
    static int N;
    static List<int[]>[] graph;

    static class Node{
        int dest, cost;
        List<Integer> list;

        public Node(int dest, int cost){
            this.dest = dest;
            this.cost = cost;
            list = new ArrayList<>();
            list.add(dest);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        graph = new List[N+1];

        for(int i=0; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[from].add(new int[]{to, cost});
        }

        st = new StringTokenizer(br.readLine());
        int startPoint = Integer.parseInt(st.nextToken());
        int endPoint = Integer.parseInt(st.nextToken());

        Node dijkstra = dijkstra(startPoint, endPoint);

        StringBuilder sb = new StringBuilder();

        sb.append(dijkstra.cost).append('\n');

        List<Integer> list = dijkstra.list;

        sb.append(list.size()).append('\n');

        for(int i=list.size()-1; i>=0; i--){
            sb.append(list.get(i)).append(' ');
        }

        System.out.println(sb);

        br.close();
    }

    static Node dijkstra(int start, int end){
        boolean[] visited = new boolean[N+1];
        int[] dist = new int[N+1];
        Arrays.fill(dist, Integer.MAX_VALUE);

        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);

        Node node = new Node(start, 0);
        pq.offer(node);

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            
            // 조건이 충족하면 노드 최신화
            if(cur.dest == end && dist[cur.dest] == cur.cost)
                node = cur;

            if(visited[cur.dest])
                continue;

            visited[cur.dest] = true;

            for(int[] nextInfo : graph[cur.dest]){
                int next = nextInfo[0];
                int nextCost = nextInfo[1];

                if(dist[next] > cur.cost +  nextCost){
                    dist[next] = cur.cost + nextCost;
                    Node nextNode = new Node(next, dist[next]);
                    nextNode.list.addAll(cur.list); // 경로 최신화
                    pq.offer(nextNode);
                }
            }
        }

        return node;
    }
}