문제사항

골드 4단계 문제였다.

문제를 보면 이 역시도 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 문제이다.

앞전에 다익스트라 알고리즘과 벨만포드 알고리즘과 다른 점은 모든 도시의 쌍 (A, B)에 대해서 구해야한다는 점이다.

즉, 특점 시작점이 없고, 임의의 모든 노드의 쌍의 최단거리를 구해야 한다.

이 때는 플로이드-워셜 알고리즘을 사용해야 한다.

'플로이드-워셜' 란?

그래프에서 최단 거리를 구하는 알고리즘은 다익스트라, 벨만포드, 플로이드 워셜이 있다.

플로이드-워셜은 모든 노드 간에 최단경로 탐색을 요구한다.

특징은 벨만포드와 마찬가지로 음수 가중치 에지가 있어도 수행 가능하다는 점이다.

또한 동적 계획법 원리를 이용해 알고리즘 접근해야한다.

시간복잡도는 특이하게 O(V^3) 를 가진다. (노드수 : V)

다른 알고리즘에 비해 꽤 느린 시간복잡도를 가지고 있기 때문에 값의 범위를 잘 살펴보아야 한다.

만약 N이 시간복잡도를 신경써야할 만큼의 큰 수가 주어진다면 플로이드-워셜을 사용하면 안된다.

N의 크기가 100, 200 정도의 작은 수로 주어졌을 때 사용 가능하다.

플로이드-워셜의 핵심이론

A 노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다.

색칠된 에지 경로가 1 → 5 최단 경로라면 1 → 4 최단 경로와 4 → 5 최단 경로 역시 색칠된 에지로 이뤄질 수 밖에 없다.

도출한 플로이드-워셜 점화식

D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E])

K는 S와 E 사이에 있는 모든 노드를 거쳐갔을 때 가장 최적 값을 K에 넣어준다.

1. 리스트를 선언하고 초기화하기

• S와 E의 값이 같은 칸은 0, 다른 칸은 무한대로 초기화한다.

• S==E는 자기 자신에게 가는 데 걸리는 최단 경로값을 의미하기 때문이다.

2. 최단 거리 리스트에 그래프 데이터 저장하기

• 출발 노드 S, 도착노드 E, 에지 가중치 W라고 했을 때 D[S][E] = W 에지 정보 리스트에 입력한다.

• “인접 행렬” 로 표현

3. 점화식으로 리스트 업데이트하기

• 기존에 구했던 점화식을 3중 for문 형태로 반복해 리스트 값 업데이트

• 완성된 리스트는 모든 노드 간의 최단 거리를 알려준다.

• 예를 들어 1번 노드에서 5번까지 가는 최단 거리는 D[1][5]=6으로 나타난다는 것을 알 수 있다.

• 플로이드-워셜 알고리즘은 모든 노드 간의 최단 거리를 확인해 주기 때문에 시간 복잡도가 O(V^3)으로 빠르지 않은 편이다.

  • 따라서 노드 개수 범위가 다른 그래프에 비해 적게 나타나는 것을 알 수 있다.

알고리즘 분류

그래프 (플로이드-워셜)

코드

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

public class Main
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] D = new int[N + 1][N + 1];

        // INF 값을 100,000,000으로 설정 (최대 비용 100,000 * 최대 도시 수 100)
        final int max_cost = 100000000;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i == j) {
                    D[i][j] = 0;
                } else {
                    D[i][j] = max_cost;
                }
            }
        }

        for (int i = 0; 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());
            // ex> "1 4 1"과 "1 4 2"가 입력으로 들어왔으면, "1 4 1"을 택해야 함.
            D[a][b] = Math.min(D[a][b], c);
        }

        //플로이드-워셜
        for (int K = 1; K <= N; K++) {
            for (int S = 1; S <= N; S++) {
                for (int E = 1; E <= N; E++) {
                    D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (D[i][j] == max_cost) {
                    D[i][j] = 0;
                }
                sb.append(D[i][j]).append(" ");
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}