[백준 11404]플로이드 (Java) - 플로이드 워셜

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

플로이드

문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

예제 입력 1 복사

5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
3 5 10
3 1 8
1 4 2
5 1 7
3 4 2
5 2 4

예제 출력 1 복사

0 2 3 1 4
12 0 15 2 5
8 5 0 1 1
10 7 13 0 3
7 4 10 6 0

 

---

풀이

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));
        int N = Integer.parseInt(br.readLine()); // 도시 개수 (노드 개수)
        int M = Integer.parseInt(br.readLine()); // 버스노선 개수 (에지 개수)
        int[][] D = new int[N+1][N+1]; // 거리인접행렬 (도시번호 1번부터 시작)
        int INF = 100000000;

        // 인접행렬 초기화 (자기자신과의 거리 : 0, 그 외는 무한대)
        for(int i=1; i<N+1; i++){
            for(int j=1; j<N+1; j++){
                if(i==j){
                    D[i][j] = 0;
                }else{
                    D[i][j] = INF;
                }
            }
        }

        // 노선정보 입력받기
        for(int i=0; i<M; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken()); // 출발도시
            int E = Integer.parseInt(st.nextToken()); // 도착도시
            int cost = Integer.parseInt(st.nextToken()); // 비용

            // 기존값, 현재 들어오는 값 중 최솟값 입력
            D[S][E] = Math.min(D[S][E], cost);
        }

        // 최단거리 비교 (플로이드워셜 알고리즘)
        for(int K=1; K<N+1; K++){
            for(int S=1; S<N+1; S++){
                for(int E=1; E<N+1; E++){
                    if(D[S][K] == INF || D[K][E] == INF) continue;
                    D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int S=1; S<N+1; S++){
            for(int E=1; E<N+1; E++){
                if(D[S][E] == INF){
                    bw.write("0 ");
                }else{
                    bw.write(D[S][E]+" ");   
                }
            }
            bw.write("\n");
        }

        bw.flush();
        bw.close();
    }
}

 

• 플로이드 워셜을 활용한 문제
  • 음수 가중치 에지가 있어도 수행할 수 있으나 음수사이클이 있으면 안된다.
  • 플로이드 워셜 알고리즘은 그래프에서 최단거리를 구하는 알고리즘이다.
  • 최단거리를 구하는 알고리즘에는 다익스트라, 벨만포드, 플로이드 워셜이 있다.
  • 플로이드 워셜은 3중 for문을 이용하기 때문에 노드의 개수가 1000이상이면 쓸 수 없다.
  • 최대 노드의 개수가 100 ~ 200개정도라면 쓸 수 있다. 이문제는 플로이드 워셜 써보라고 판을 깔아준 문제이기 때문에 플로이드 워셜로 풀었다. 
• 도시개수 N(노드), 노선개수 M(에지)를 입력으로 받는다.
• 도시번호가 1번부터 시작하므로 인접행렬 2차원 배열 N+1크기로 선언해준다.
• 자기자신과의 거리는 0, 그외는 INF로 초기화해준다. 
• 이때 INF의 크기는 충분히 큰 100000000로 선언해주었다. 
  • 애매하게 10001로 했더니, 백준에서 오답판정을 하였다.
  • 처음에는 Integer.MAX_VALUE를 사용했는데, 그러면 max값끼리 더할 때 오버플로우가 발생해서 아예 큰음수값이 나와서 답이 제대로 계산되지 않는다.
• 그다음 M개의 줄을 입력으로 받아서 노선정보를 받는다. 이때 S -> E 경로가 중복되서 나오기도 하므로, 최솟값을 비교해서 입력값을 넣어주어야 한다.

플로이드워셜 알고리즘을 통해 최단거리를 비교해준다.

• 이때 3중 for문을 도는데, 부분경로 K가 제일 바깥에 위치하여야 한다.

플로이드-워셜 알고리즘의 핵심 개념

• 그래프에서 모든 노드 쌍 (S, E) 간의 최단 거리를 찾는 알고리즘.
• 특정 노드 K를 중간 경유지로 고려하여 기존 경로보다 더 짧은 경로가 있으면 업데이트.
• 점진적으로 경유할 수 있는 노드를 추가하면서 최단 경로를 완성해 나감.

왜 K가 가장 바깥쪽 루프에 있어야 할까?

• 플로이드 워셜 알괼즘에서 K가 가장 바깥쪽 루프에 위치하는 이유는, 
• 각 노드 K를 "중간 경유지"로 고려하면서 점진적으로 최단 경로를 업데이트 해야 하기 때문이다.

3중 for문에서 K가 바깥쪽인 이유

for (int K = 1; K <= N; K++) {  // 1️⃣ 경유 노드 K를 설정 (가장 바깥)
    for (int S = 1; S <= N; S++) {  // 2️⃣ 출발 노드 S
        for (int E = 1; E <= N; E++) {  // 3️⃣ 도착 노드 E
            if (D[S][K] != INF && D[K][E] != INF) {  // K를 거쳐갈 수 있는 경우
                D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]);
            }
        }
    }
}

✅ K를 가장 바깥에 두는 이유

1️⃣ K를 하나씩 늘려가면서 점진적으로 업데이트해야 함

• 처음에는 K=1만 경유할 수 있도록 고려
• 그다음 K=2, K=3... 점점 더 많은 중간 경유지를 활용
• 즉, K를 하나씩 늘려가면서 갱신해야 올바른 최단 경로를 얻을 수 있음

2️⃣ K를 가장 안쪽 루프에 두면, 미완성된 경로를 사용하게 됨 (잘못된 결과)

• 만약 K를 가장 안쪽 루프에 둔다면,
  아직 모든 S → K나 K → E 경로가 충분히 업데이트되지 않은 상태에서
  미완성된 정보로 업데이트를 진행할 위험이 있음.
• K를 점진적으로 늘려가면서 탐색해야 안정적인 최단 경로를 구할 수 있음.