[BOJ/Floyd-Warshall] 백준 11404 - 플로이드 / 11780 - 플로이드 2 (Java)

11404 - 플로이드

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

문제

모든 도시 쌍 (a, b)에 대해 도시 a에서 b로 가는데 필요한 비용의 최솟값

입력
첫째 줄: 도시의 개수 n (2 <= n <= 100)
둘째 줄: 버스의 개수 m (1 <= m <= 100,000)
셋째 줄 ~ m+2줄: 버스의 정보
버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c
시작 도시와 도착 도시가 같은 경우 X, 비용 (자연수) <= 100,000
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음
출력
n개의 줄 출력
i번째 줄에 출력하는 j번째 숫자: 도시i에서 j로 가는데 필요한 최소 비용
만약, i에서 j로 갈 수 없는 경우 0 출력

---

풀이

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)

모든 도시 쌍 (i, j) 간의 최소 이동 비용 구하기

 

• `map[i][j]`: 도시 i에서 j로 가는 최소 비용
  • `i == j`: 자기 자신 => 0
  • 나머지: 처음에는 도달할 수 X 상태 -> `INF`로 초기화
    • `static final int INF = 1_000_000_000`
    • -> `map[a][b] = Math.min(map[a][b], c)`

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

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j) map[i][j] = 0;
        else map[i][j] = INF;
    }
}

 

• 경유지 k, 출발지 i, 도착지 j
  • i -> j (기존 경로) > i -> k -> j (최신 경로) => 갱신
  • => 모든 도시 쌍 간 최단 경로

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

---

코드

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

// 플로이드
public class boj_11404 {
    static int[][] map;
    static final int INF = 1_000_000_000;;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        map = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) map[i][j] = 0;
                else map[i][j] = INF;
            }
        }

        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());
            map[a][b] = Math.min(map[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 (map[i][k] + map[k][j] < map[i][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (map[i][j] == INF) sb.append("0 ");
                else sb.append(map[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

---

11780 - 플로이드 2

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

문제

모든 도시 쌍 (a, b)에 대해 도시 a에서 b로 가는데 필요한 비용의 최솟값

입력
첫째 줄: 도시의 개수 n (2 <= n <= 100)
둘째 줄: 버스의 개수 m (1 <= m <= 100,000)
셋째 줄 ~ m+2줄: 버스의 정보
버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c
시작 도시와 도착 도시가 같은 경우 X, 비용 (자연수) <= 100,000
시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음
출력
n개의 줄 출력
i번째 줄에 출력하는 j번째 숫자: 도시i에서 j로 가는데 필요한 최소 비용
만약, i에서 j로 갈 수 없는 경우 0 출력
nxn개의 줄을 출력
ixn+j번째 줄: 도시 i에서 j로 가는 최소 비용에 포함되어 있는 도시 개수 k 출력
도시 i에서 j로 가는 경로 출력 (공백)
이때, 도시 i와 j도 출력해야 함
만약, i에서 j로 갈 수 없는 경우 0 출력

---

풀이

for (int i = 1; i <= n; i++) {
    Arrays.fill(dist[i], INF);
    dist[i][i] = 0;
}

 

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

 

---

코드

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

// 플로이드 2
public class boj_11780 {
    static final int INF = 1_000_000_000;;
    static int[][] dist, path;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        dist = new int[n + 1][n + 1];
        path = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], INF);
            dist[i][i] = 0;
        }

        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());

            if (c < dist[a][b]) {
                dist[a][b] = c;
                path[a][b] = 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][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        path[i][j] = path[i][k];
                    }
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == INF) sb.append("0 ");
                else sb.append(dist[i][j]).append(" ");
            }
            sb.append("\n");
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] == INF || i == j) {
                    sb.append("0\n");
                } else {
                    List<Integer> arr = new ArrayList<>();
                    int cur = i;
                    while (cur != j) {
                        arr.add(cur);
                        cur = path[cur][j];
                    }
                    arr.add(j);

                    sb.append(arr.size()).append(" ");
                    for (int city : arr) sb.append(city).append(" ");
                    sb.append("\n");
                }
            }
        }

        System.out.print(sb);
    }
}