[백준] 11404*/ 플로이드 (골드4)

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

다익스트라 vs 플로이드-워셜

다익스트라>

• '하나의 출발점'에서 다른 모든 곳까지의 최단 거리를 찾는 알고리즘 (1:N 관계)
• 우선순위 큐를 사용하면 O((V+E)logV), 우선순위 큐를 사용하지 않고 선형 탐색을 하면 O(V^2)
• 그리디
• 출발점 중심

플로이드-워셜>

• '모든 지점'에서 '모든 다른 지점'까지의 최단 거리를 한 번에 구하는 알고리즘 (N:N 관계)
• O(V³)
• DP
• 경유지 중심

=> 여기서 다익스트라를 사용하면 오버헤드가 더 많이 발생함

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        int[][] city = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) city[i][j] = 0;
                else city[i][j] = Integer.MAX_VALUE;
            }
        }
        for(int i=0;i<m;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            // 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다
            city[from][to]=Math.min(city[from][to],val);
        }

        // 거리 최소값 구하기
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(city[i][j] > city[i][k]+city[k][j]){
                        city[i][j] = city[i][k]+city[k][j];
                    }
                }
            }
        }

        // 각 항목에서 갈 수 있는 최소값 출력
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                System.out.print(city[i][j]+" ");
            }
            System.out.println();
        }

    }
}

=> 틀림

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n,m;
    static int INF = 100*100_000 + 1;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        int[][] city = new int[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j) city[i][j] = 0;
                else city[i][j] = INF; // 21억 정도(Integer.MAX_VALUE) > v*e이지만 더하면서 오버플로우 발생
            }
        }
        for(int i=0;i<m;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int val = Integer.parseInt(st.nextToken());
            // 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다
            city[from][to]=Math.min(city[from][to],val);
        }

        // 거리 최소값 구하기
        for(int k=1;k<=n;k++){
            for(int i=1;i<=n;i++){
                for(int j=1;j<=n;j++){
                    if(city[i][j] > city[i][k]+city[k][j]){
                        city[i][j] = city[i][k]+city[k][j];
                    }
                }
            }
        }

        // 각 항목에서 갈 수 있는 최소값 출력
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                // i에서 j로 갈 수 없는 경우
                if(city[i][j] == INF) System.out.print(0+" ");
                else System.out.print(city[i][j]+" ");
            }
            System.out.println();
        }

    }
}

10/16 다시 풀기 완