백준 - 11404 플로이드(feat.플로이드 와샬 알고리즘)

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

11404번: 플로이드

 

---

플로이드 와샬 알고리즘 - Floyd Warshall

플로이드 와샬 알고리즘은 모든 정점에서 모든 정점까지 최단 경로를 구하는 것이다.

이때 임의의 노드 S 에서 E 까지 가는데 걸리는 최단 거리를 구하기 위해 S 와 E 사이의 노드인 M 에 대해서 S에서 M 까지 걸리는 최단 거리와 M 에서 E 까지 걸리는 최단 거리를 이용한다.

 

아래 사진으로 이야기하자면 1에서 2, 3, 4, 5 까지의 최단 거리, 2에서 1,3,4,5 까지의 최단거리 --- 해서 구하는 것이다.

따라서 그림은 아래의 표처럼 최단 경로가 설정 될 것이다.

출처 : https://ssungkang.tistory.com/227

대략적으로 표로 정리하면 아래와 같은 모양이 된다. 표에서 0 으로 넣어둔 곳은 자기 자신에서 자기 자신에게로 가는 경우를 표기하기 위함이고,. INF 는 출발점에서 부터 도작점까지 이동하는 경로가 없음을 표시하기 위함이다.

	1	2	3	4	5
1	0	3	8	INF	-4
2	INF	0	INF	1	7
3	INF	4	0	INF	INF
4	2	INF	-5	0	INF
5	INF	INF	INF	6	0

 

그렇다면 표에서 최소값을 어떻게 계산되는 것일까? 바로 출발점에서 도착점까지 갈 때, 경유지를 거쳐서 가는 경우와 직접(바로) 가는 경우를 비교해서 그 최소값을 계산하게 된다.

 

예를 들면  우리가 1에서 2 까지 방법은 아래처럼 여러가지가 나온다.

- 1 -> 2 : 3
- 1 -> 3 -> 4 : 12
등등등

 

이때 가장 작은 값을 구해야 함으로 결국 1 -> 2 까지는 3 의 비용을 갖게 된다.

 

이처럼 단순히 출발점 -> 도착점 까지의 거리가 아닌, 중간 경유지를 경유했을 때와 안 했을 때를 모두 비교해서 최소값을 찾는 것이 바로 플로이드 와샬 알고리즘이다.

 

즉, 플로이드 와샬 알고리즘의 핵심은 '거처가는 정점' 을 기준으로 최단 거리 혹은 최단 비용을 계산하는 것이다.

 

• 플로이드 와살은 위에서의 이유 때문에 3중 FOR 문을 사용하며 2차원 배열에 거리 정보를 저장하게 된다.
• 플로이드 와샬은 DP 알고리즘에 속하는데 이는 노드의 개수가 N 이라고 할 때, N 번만큼 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문이다.
• 알고리즘의 시간 복잡도는 O(N^3) 으로 노드의 개수가 N 일 때, N 번 단계를 수행하며, 단계마다 O(N^2) 의 연산을 통해 '현재 노드를 거쳐 가는 모든 경로'를 고려한다. 노드가 10 개만 되도 무려 1000 번을 반복해야함으로 계산이 오래걸리게 된다. 따라서 노드의 개수를 고려해서 사용하자!!

 

풀이 방법

문제 이름부터 "플로이드" 이기 때문에 당연히 플로이드 와샬 알고리즘을 사용하게 된다.

 

문제 풀이의 핵심은 위에서 이야기한 3중 FOR 문을 사용하는 것과 도착할 수 없는 곳은 0 으로 출력한다는 점이다. 즉 배열을 처음에 INF(최대값) 로 초기화 한 후 계산이 끝난 후에도 배열에 INF 가 남아있다면 해당 값을 0 으로 변경해서 출력해야 한다.

 

나머지는 주석 참고!!

 

package baekJoon;

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

// https://www.acmicpc.net/problem/11404
// 플로이드 와샬 알고리즘 풀이 문제
// 플로이드 와샬 알고리즘의 포인트는 3중 반복문을 사용한다는 점!!
// 때문에 시간 복잡도가 O(n^3) 이기 때문에 그래프가 커질수록 계산이 오래걸린다
public class Quiz_11404 {
    // 생각없이 MAX_VAL 로 했더니 오버플로 발생ㅠ
    static final int INF = 987654321;
    static int[][] arr;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

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


        makeGraph(n, m);
        floydWarshall(n);

    }

    static void makeGraph(int n, int m) throws IOException {
        StringTokenizer st;

        // 거리 계산을 위한 arr 배열을 가장 큰 값으로 초기화 한다.
        // 이는 결국 각 노드에 도착하는 최소 비용 을 찾기 위함이기 때문에
        // 처음에는 가장 큰 값으로 초기화 후 최소값을 비교해서 찾기 위해서 이다.
        for (int i = 1; i<= n; i++) {
            for (int j = 1; j<=n; j++) {
                arr[i][j] = INF;

                if(i == j){
                    arr[i][j] = 0;
                }
            }
        }

        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            // 출발 도시와 도착 도시가 같지만 다른 입력값이 들어올 수 있다
            // 즉 1 4 1 과 1 4 2 가 동시에 입력값이 될 수 있다.
            // 이때 우리는 1 4 1 을 선택해야 한다.
            arr[a][b] = Math.min(arr[a][b], c);
        }

    }

    static void floydWarshall(int n){
        StringBuilder sb = new StringBuilder();

        // 플로이드 와샬 알고리즘 시작
        for (int k = 1; k<=n; k++){ // 중간에 경유하는 노드에 대해서 계산하기 위한 for 문
            for (int i = 1; i<=n; i++){ // 출발지 for 문
                for(int j = 1; j<=n; j++){ // 도착지 for 문
                    // 최단경로 초기화
                    // 출발지 i 에서 도착지 j 로 직행하는 cost 보다
                    // 경유지 k 를 거치는 경우가 더 작다면 해당 값을 arr 배열에 갱신
                    if (arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        // 출력
        for (int i = 1; i<=n; i++){
            for(int j = 1; j<=n; j++){
                // 갈 수 없는 곳은 0 으로 초기화
                if(arr[i][j] == INF){
                    arr[i][j] = 0;
                }
                sb.append(arr[i][j] + " ");
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }
}

 

- Reference

https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithm

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

 

https://blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

 

https://ssungkang.tistory.com/227

[Algorithm] 플로이드 와샬(Floyd-Warshall) 알고리즘