🐳백준 11404 : 플로이드

초기 문제 접근

오랜만에 플로이드 워셜을 풀어보았다.
기억 나는 건 삼중 for문을 돌면서 경유지를 지정하고, 가장 최소의 값이 나오는 경우를 구하는 것이었다.

이 기억을 되짚어 아래와 같이 풀었다.

1) 인접 리스트로 간선 정보를 저장
2) 삼중 for문을 돌면서 출발지, 도착지, 경유지를 지정한다.
3) getWeight 메서드를 이용해 경유지를 거쳐서 가는 거리를 구한다.
int path = getWieght(출발지, 경유지) + getWeight(경유지, 도착지)
4) for문을 돌면서 최소의 path 값을 갱신한다.

위 로직으로는 답이 안 나온다.😿
gemini에게 물어보니 플로이드 워셜을 잘못 접근했다고 한다.

이참에 플로이드 워셜을 다시 정리해보자

🐟플로이드 워셜 정리

플로이드 워셜은 그래프에서 모든 노드 쌍 간의 최단 경로를 찾는 알고리즘이다.
음수 가중치를 가진 간선이 있을 때도 사용할 수 있다는 장점이 있다.

🦀핵심 원리

중간 노드(경유지)를 허용하면서 최단 경로를 점진적으로 개선

1. 삼중 반복문
1) 가장 바깥쪽 : 경유지 노드
2) 중간 : 출발 노드
3) 안쪽 : 도착점

2. 점화식
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])

🦀코드 흐름

1) dist 배열 생성 및 초기화

• 문제 조건에 따라 자기자신은 0으로, 나머지는 무한대로

		// dist 배열 생성
		dist = new int[n + 1][n + 1];

		// dist 배열 초기화 //자기 자신은 0으로 두기. 나머지는 무한대로
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (i == j) {
					dist[i][j] = 0;
				} else {
					dist[i][j] = INF;
				}
			}
		}

2) 삼중 for문으로 플로이드 워셜 알고리즘 돌리기

		// 플로이드 워셜 알고리즘 (3중 for문)
		// k는 경유 노드
		for (int k = 1; k <= n; k++) {
			// i : 출발지점
			for (int i = 1; i <= n; i++) {
				// j : 도착지점
				for (int j = 1; j <= n; j++) {
					// i에서 j로 가는 기존 경로와 k를 거쳐서 가는 경로 비교
					// 경로가 있을 때 수행
					if (dist[i][k] != INF && dist[k][j] != INF) {
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
					}

				}
			}
		}

🦀잘못 접근한 부분

1. 현재까지 계산된 최단 거리 배열(dist)을 사용해야 한다.

인접 리스트 static List<Edge>[] graph를 사용하는 것이 아닌 2차원 배열을 사용해야 한다.

내가 만든 getWeight() 함수는 여러 개의 간선이 있을 경우, 처음 만나는 간선 하나만 탐색한다는 한계가 있다.

2. 삼중 for문의 순서
경유지 > 출발지 > 도착지 순으로 해야한다.

코드

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

public class backjoon_floyd_11404_Solution {

    // 문제의 비용은 최대 100,000. 도시 개수 n=100.
    // 최대 경로 비용은 100 * 100,000 = 10,000,000.
    // 무한대(INF) 값은 이보다 커야 합니다. int의 MAX_VALUE는 오버플로우 위험이 있습니다.
    // 100,000,001 (1억) 정도로 설정하면 충분합니다.
    static final int INF = 100_000_001; 
    static int n;
    static int[][] dist; // 최단 거리를 저장할 2차원 배열

    public static void main(String[] args) throws IOException {
        // System.setIn(new FileInputStream("src/input.txt")); // 파일 입력은 테스트용으로만 사용

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        // 1. dist 배열 초기화: 자기 자신은 0, 나머지는 INF
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = INF;
                }
            }
        }

        // 2. 간선 정보로 dist 배열 채우기 (직접 연결된 간선 중 최소 비용 선택)
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            // 같은 노선이 여러 개 주어지면 더 작은 비용으로 초기화
            dist[from][to] = Math.min(dist[from][to], w); 
        }

        // 3. 플로이드-워셜 알고리즘 실행 (삼중 반복문)
        // k: 중간 지점 (경유 노드)
        for (int k = 1; k <= n; k++) {
            // i: 출발 지점
            for (int i = 1; i <= n; i++) {
                // j: 도착 지점
                for (int j = 1; j <= n; j++) {
                    // i에서 j로 가는 기존 경로와 i에서 k를 거쳐 j로 가는 경로 비교
                    if (dist[i][k] != INF && dist[k][j] != INF) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }

        // 4. 결과 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 갈 수 없는 경우 (INF)는 0으로 출력
                if (dist[i][j] == INF) {
                    sb.append(0).append(" ");
                } else {
                    sb.append(dist[i][j]).append(" ");
                }
            }
            sb.append("\n");
        }
        
        System.out.print(sb.toString());
    }
}