백준 1719번: 택배 - 플로이드와샬 Java

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

1719번: 택배

 

1. 플로이드 와샬에서 3중 for문을 작성할 때 i, j, k 의 순서가 중요하다

 

2. 플로이드 와샬에서 k노드를 통해 경로를 업데이트 할 때마다 k노드는 도착점 이전의 가장 마지막 노드가 된다.

따라서 출발점 이후 첫번째 노드를 구하려면

 

현재 문제에서 그래프가 양방향 그래프이기 때문에 출발점 도착점 기준 가장 마지막 노드가

도착점 출발점의 첫번째 노드가 된다.

 

이를 이용하면 추가적인 재귀나 반복 없이 첫번째 노드를 구할 수 있다.

 

import java.util.*;


class Edge implements Comparable<Edge>{
    int x, c;

    Edge(int x, int c){
        this.x = x;
        this.c = c;
    }

    @Override
    public int compareTo(Edge e){
        return c- e.c;
    }
}


public class Main {
    static int[][] ans, dist,  adj;
    static int n, m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        ans = new int[n+1][n+1];
        dist = new int[n+1][n+1];
        adj = new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE/2);
            Arrays.fill(adj[i],Integer.MAX_VALUE/2);
            adj[i][i] = 0;
            dist[i][i] = 0;
        }

        for(int i=0; i<m; i++){
            int a= sc.nextInt();
            int b =sc.nextInt();
            int c = sc.nextInt();

            dist[a][b] = Math.min(dist[a][b],c);
            dist[b][a] = Math.min(dist[b][a],c);


            ans[a][b] = a;
            ans[b][a] = b;
        }


        for(int k=1; k<=n;k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    if(dist[i][j] > dist[i][k] + dist[k][j]){
                        dist[i][j] = dist[i][k] + dist[k][j];
                        ans[i][j] = ans[k][j];
                    }
                }
            }
        }

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(i==j) System.out.print("- ");
                else System.out.print(ans[j][i] + " ");
            }
            System.out.println();
        }
    }
}