백준 | 11404번. 플로이드 - 최단경로 (플로이드) 문풀

⬛ 백준 11404번. 플로이드  - 최단경로 (플로이드 문풀)

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

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을 출력한다.

---

💚 문제 접근 방식

• 이 문제에서는 ‘모든 도시의 쌍에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값’을 구하라고 했다.
• All-to-All 문제 (플로이드 문제) 이다.
• 플로이드는 이차원 배열로 distance[][] 를 두고, N개 도시에 대한 N개 도시로의 최단 거리를 모두 구해주어야 한다.

   1) 초기화 : distance[][]는 i==j 즉, 자신에 대한 정점 거리 0처리, 그 외에는 INF값으로 초기화한다.

   2) 데이터를 입력 받는다. 여기서는 a → b로의 가중치 c 순으로 들어온다.

   3) 플로이드는 3중 for문을 돈다.

      가장 바깥 for문에서 k는 각 도시들을 경유지로서 지칭한다.

//플로이드 적용 
for(int k=1; k<=N; k++) { //경유지 k로 순회하면서 
    //모든 도시 i -> j 로 가는 최단 경로 갱신할 건데 
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            //기존 i->j 경로보다, k 경유해서 i-> k -> j로 가는 값이 더 작다면 갱신 
            if(distance[i][j] > distance[i][k] + distance[k][j]) {
                distance[i][j] = distance[i][k] + distance[k][j];
            }
        }
    }
}

---

[주의] INF를 Integer.MAX_VALUE로 두면 안되는 이유 : 오버플로우

이상하게 나온 출력값

그렇다. INF값을 Integer_MAX_VALUE 로 초기화해두면, 최단거리로 갱신하는 과정에서 초반 부에 (distance[i][k] + distance[k][j])를 처리할 떄, 이미 int형 범위를 넘어 음수로 갱신되버린 거다. 이렇게 되면, 후반부에는 해당 음수가 이미 작은 값이라서 추후 최단 경로의 값으로 갱신이 안되기 때문에 최단거리를 못구해버리는 불상사를 낳는다. 심지어 예전에 풀었을 때도 같은 문제를 맞닥뜨렸었는데 다시 풀면서 또 같은 실수를 반복했다. 뇌 챙겨

GPT의 조언 ㅎㅎ

🏓 INF 의 값 적절히 설정하는 법

• 간선 가중치의 최댓값 X (정점 개수 -1) 보다 큰 값을 사용하면 된다.
• 이 문제에서는 1) m = 최대 100,000 개 2) n = 100개 이다.
• 그래서 INF 값은 10^5 * 10^2 +1 = 10000001 로 설정하면 오버플로우 될 일이 없다.

---

💚 제출 코드

import java.util.*;

/**
 * 11404번. 플로이드 문풀 - 플로이드 all-to-all
 * @author MYLG
 *
 */
public class Main {
	static final int INF = 10000001; //이거 주읭 
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		int N = kb.nextInt();
		int M = kb.nextInt();
		
		int[][] distance = new int[N+1][N+1];
		
		//초기화 		
		for(int i=1; i<=N; i++) {
			for(int j =1; j<=N; j++) {
				if(i == j) distance[i][j] = 0;
				else distance[i][j] = INF;
			}
		}
		
		//데이터 입력
		for(int i =0; i<M; i++) {
			int a = kb.nextInt();
			int b = kb.nextInt();
			int val = kb.nextInt();
			
			if(distance[a][b] < val) continue;
			distance[a][b] = val;//세팅 
		}
		
		//플로이드 적용 
		for(int k=1; k<=N; k++) {
			for(int i=1; i<=N; i++) {
				for(int j=1; j<=N; j++) {
					if(distance[i][j] > distance[i][k] + distance[k][j]) {
						distance[i][j] = distance[i][k] + distance[k][j];
					}
				}
			}
		}
		
		//출력
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				if(distance[i][j] == INF) {
					System.out.print("0 ");
				}else {
					System.out.print(distance[i][j] + " ");
				}
			}
			System.out.println();
		}
	}
}