[JAVA] 백준 택배 1719

 

 

각 집하장들이 있고 하나의 집하장에서 또다른 집하장까지의 최소 거리를 구하되 해당 집하장으로 가기위해서 처음 들려야하는 집하장을 구하는 문제이다.

즉 집하장 1에서 집하장 5로 가기위해서는 5라는 비용이 들고 해당 위치로 가기 위해서는 집하장 2를 먼저 가야한다.

 

먼저 해당 거리까지의 최소 비용을 구한 후  이동할 때 map라는 공간에 어디서 출발했는지를 저장해 놓고 뒤로 돌면서 찾는 방식으로 해결하였다.

 

// Online Java Compiler
// Use this editor to write, compile and run your Java code online
import java.util.*;
import java.io.*;
class Main {
    static class Node{
        int v;
        int w;
        int before; 
        Node(int v, int w, int before){
            this.v =v;
            this.w = w;
            this.before = before;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        String[] input =br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        
        
        ArrayList<ArrayList<Node>> edge = new ArrayList<>();
        for(int i =0; i<=n; i++){
            edge.add(new ArrayList<Node>());
        }
        
        int[][] map = new int[n+1][n+1];
        
        for(int i =0; i<m; i++){
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int w = Integer.parseInt(input[2]);
            edge.get(a).add(new Node(b, w,0));
            edge.get(b).add(new Node(a, w,0));
        }
        for(int i =1; i<=n; i++){
            PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.w-o2.w); 
            int[] dist = new int[n+1];
            Arrays.fill(dist, Integer.MAX_VALUE);
            pq.offer(new Node(i, 0, 0));
            dist[i] = 0;
            while(!pq.isEmpty()){
                Node node = pq.poll();
                int v= node.v;
                int w = node.w;
                int b = node.before;
                if(w > dist[v]) continue;
                for(Node no: edge.get(v)){
                    int t = no.v;
                    int tw = no.w + w;
                    int before = v;
                    if(tw < dist[t]){
                        dist[t] =tw;
                        if(map[i][v] ==0){
                            map[i][t] = t;    
                        }else{
                            ;
                            while(map[i][before] != before){
                               before = map[i][before]; 
                            }
                            map[i][t] =before;
                        }
                        
                        
                        pq.offer(new Node(t, tw, v));
                    }
                }
            }
        }
        for(int i =1; i<=n; i++){
            for(int j =1; j<=n; j++){
                if(i == j){
                    bw.write("- ");
                }else{
                    bw.write(map[i][j] + " ");
                }
            }
            bw.write("\n");
        }
        
        
        
        
        bw.flush();
        bw.close();
        br.close();
    }
}