BOJ_11404 : 플로이드

👉 문제링크

11404번: 플로이드

---

---

🔸 문제 분석 🔸

• 플로이드-워셜 알고리즘의 기초 문제이다.

🔸 문제 풀이 🔸

• 단방향 가중치 연결 그래프에서 모든 경로에 대한 최단 거리를 구한다.

🔸 코드 🔸

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        int[][] cost = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j)
                    cost[i][j] = Integer.MAX_VALUE;
            }
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            cost[a][b] = Math.min(cost[a][b], c);
        }

        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (cost[i][k] != Integer.MAX_VALUE && cost[k][j] != Integer.MAX_VALUE)
                        cost[i][j] = Math.min(cost[i][j], cost[i][k] + cost[k][j]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (cost[i][j] == Integer.MAX_VALUE)
                    sb.append(0).append(' ');
                else
                    sb.append(cost[i][j]).append(' ');
            }
            sb.append('\n');
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• n x n 행렬을 만들어 가중치를 저장한다.
  • 단방향 연결이며 자기 자신은 0, 연결이 안되어 있으면 Infinity로 저장한다.
• k를 경유지로하는 i -> j 연결을 모두 확인해 최소값을 갱신한다.
• 모든 i -> j 값을 출력한다.

---

🔸 end 🔸

• 플로이드 워셜 문제는 많이 풀이보지 않았는데, 알고리즘을 알고나면 간단히 풀이할 수 있었다.
  • 핵심은 k를 경유지로 두고, 최소값을 업데이트하는 점화식이었다.
• 단방향 연결을 양방향 연결로 착각해 1회 틀렸다.