[JAVA] 백준 11404번 : 플로이드

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

11404번: 플로이드

---

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

public class Main {
    final static int INF = 100000001;
    static int start, end, cost;
    static StringTokenizer st;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        int[][] edge = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            Arrays.fill(edge[i], INF);
            edge[i][i] = 0;
        }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());
            cost = Integer.parseInt(st.nextToken());
            edge[start][end] = Math.min(edge[start][end], cost); //최소비용 갱신
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if(edge[i][k] != INF && edge[k][j] != INF)
                        edge[i][j] = Math.min(edge[i][k] + edge[k][j], edge[i][j]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (edge[i][j] == INF)
                    sb.append(0).append(" ");
                else
                    sb.append(edge[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }
}

💡 플로이드-워셜

풀이

플로이드-워셜 : D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) (K : 경유 지점)
인접 행렬을 사용해 풀이, 가중치가 나와있는 경우를 제외하고 모든 칸을 INF로 세팅해놓은 뒤, 점화식을 통해 배열 값 업데이트 함 (=> 3중 for문 (1) 경유지 K에 대해, (2) 출발 노드 S에 대해, (3) 도착 노드 E에 대해)

• 노드 (= 도시) 개수가 적으므로 3중 for문 돌려도 괜찮음 >> 2개의 도시를 잇는 노선이 하나가 아닐 수 있으므로 플로이드-워셜을 사용해보자
• 최소 거리를 구해야 하므로 두 지점을 잇는 경로가 여러 개 존재하는 경우, 최솟값을 비교해 기록해 사용하자