[Algorithm] 백준_최소비용 구하기 2_11779번 (JAVA)

📝문제

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

최비용 구하기 2 : 11779번

티어 : 골드3

💡풀이

문제 유형

다익스트라

 

걸린 시간

110분

 

시간 복잡도

 

 

풀이 방법 도출

1. 이제 가중치가 다른 경로 사이의 최소 비용 구하기 하면 바로 다익스트라가 떠오른다.
2. 이틀 전에 풀었던 최소비용 구하기 문제와 거의 흡사하나 출력 조건에 몇가지 추가 되었다 (https://girokeulhaja.tistory.com/135)
3. 우선순위 큐를 사용하여 인접한 배열 리스트를 검사해 최소비용을 갱신해준다.
4. 지나간 경로 출력 하는 방법을 모르겠어서 지피티한테 물어봤다,,
5. 그리고 StringBuilder 의 reverse() 메서드를 사용하려고 했으나 1 10 100으로 들어온 경우
6. 001 01 1이 출력 되므로 ArrayList로 받기로 한다.

import java.util.*;
import java.io.*;
class Main{
    static ArrayList<Node>[] graph;
    static int[] dist;
    static int[] path;
    static int INF = Integer.MAX_VALUE;
    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()); //버스의 개수

        dist = new int[n+1];
        path = new int[n+1];
        Arrays.fill(dist, INF);
        Arrays.fill(path, -1);

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

        StringTokenizer st;

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[start].add(new Node(end, cost));
        }

        st = new StringTokenizer(br.readLine());
        int u = Integer.parseInt(st.nextToken());
        int v = Integer.parseInt(st.nextToken());

        dist[u] = 0;
        dijkstra(u);

        System.out.println(dist[v]);

        StringBuilder sb = new StringBuilder();
        int now = v;
        ArrayList<Integer> list = new ArrayList<>();
        while(true){
            list.add(now);
            if(now == u) break;
            now = path[now];
        }

        Collections.reverse(list);
        for(int l : list){
            sb.append(l).append(" ");
        }
        System.out.println(list.size());
        System.out.println(sb);
    }
    public static void dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b)->a.cost);
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node node = pq.poll();
            int now = node.end;
            int cost = node.cost;

            if(cost > dist[now]) continue;

            for(Node next : graph[now]){
                int newCost = dist[now] + next.cost;
                if(newCost < dist[next.end]){
                    dist[next.end] = newCost;
                    path[next.end] = now;
                    pq.add(new Node(next.end, newCost));
                }
            }
        }
    }
}
class Node{
    int end;
    int cost;
    public Node(int end, int cost){
        this.end = end;
        this.cost = cost;
    }
}

 

🤔Review

다익스트라는 껌이지 이제