[백준] 11779번 : 최소비용 구하기 2

11779번: 최소비용 구하기 2

---

[다익스트라]

입력으로 출발 정점과 도착 정점이 주어지므로 한 정점에서 모든 정점으로의 최단 거리를 구하면 된다. 이 문제는 무난한 다익스트라 문제같이 보이나, 출발 정점 ~ 도착 정점 최단 거리의 경로를 구해야 한다. 나는 이 과정을 Dijkstra() 내에서 구현하였다.

 

int[] from 라는 배열에 다음 정점을 방문하기 전에 어디서 왔는지에 대한 정보를 적었다. ( from[next] = current )

 

아무튼 이건 포스팅하지 않았었는데.. 재채점 결과 TLE를 받아 다시 풀게되었다. 이전의 코드는 다익스트라 내에서 다음과 같이 적어놨었다.

//이전 코드
                if(distance[next] >= nextDistance){
                    distance[next] = nextDistance;

                    from[next] = current;
                    Q.add(new Edge(next, nextDistance));
                }

//현재 코드
                if(distance[next] > nextDistance){
                    distance[next] = nextDistance;

                    from[next] = current;
                    Q.add(new Edge(next, nextDistance));
                }

다익스트라에서 '>'와 '>='는 아주 큰 차이임이 분명하다. 이와 더불어 출력 부분에서도 변경된 것이 있는데, 이전에는 코딩 테크닉이 부족하여 컬렉션을 사용했었다. 지금은 배열만으로 해결할 수 있어 좋았다.

# Code </>

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

public class Main {

    static class Edge implements Comparable<Edge>{
        int tg, d;
        public Edge(int t, int dt){
            tg=t;
            d=dt;
        }
        @Override
        public int compareTo(Edge o) {
            return d-o.d;
        }
    }
    
    static List<Edge>[] list = new ArrayList[1001];
    static final int INF = 1000000000;
    static int[] distance = new int[1001], from = new int[1001];

    static void Dijkstra(int start) {
    
        Queue<Edge> Q = new PriorityQueue<>();
        distance[start] = 0;
        Q.add(new Edge(start, 0));

        while(!Q.isEmpty()){
            Edge edge = Q.poll();
            int current = edge.tg;
            int d = edge.d;

            if(distance[current] < d) continue;

            for(int a=0; a<list[current].size(); a++){
                Edge nextEdge = list[current].get(a);
                int next = nextEdge.tg;
                int nextDistance = d + nextEdge.d;

                if(distance[next] > nextDistance){
                    distance[next] = nextDistance;

                    from[next] = current;
                    Q.add(new Edge(next, nextDistance));
                }
            }
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++) {
            distance[i] = INF;
            from[i] = i;
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int og = Integer.parseInt(st.nextToken());
            int tg = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            
            list[og].add(new Edge(tg, d));
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        Dijkstra(start);

        int tmp = end, idx = 0, cnt = 0;
        int[] result = new int[1001];

        while(true) {
            result[idx++] = tmp;
            cnt++;

            if (tmp == start) break;
            tmp = from[tmp];
        }

        System.out.println(distance[end]);
        System.out.println(cnt);
        
        for(int i=idx-1; i>=0; i--)
            System.out.print(result[i] + " ");
    }
}