[백준] 11404번 - 플로이드

 

11404번: 플로이드

 

 

 

 

 

문제

 

n개의 도시가 존재하고 도시 A에서 출발하여 도시 B에 도착하는 비용 c의 버스 정보가 M개 주어질 때, 모든 도시의 쌍 (A, B)에 대하여 도시 A에서 도시 B로 가는데 필요한 비용의 최솟값을 구하여라.

 

 

 

 

 

조건

 

시작 도시와 도착 도시가 같은 경우는 없다.

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

도시 i에서 도시 j로 갈 수 없는 경우에는 0 출력

2 <= n <= 100

1 <= m <= 100,000

1 <= 비용 <= 100,000

시간 제한 1초

 

 

 

 

 

풀이 방향

 

도시를 정점이라고 생각하고 도시의 쌍 (A, B)를 두 도시 A, B의 간선이라고 생각하면, 가중치가 있는 양방향 그래프로 치환하여 문제를 해결할 수 있다. 또한 그래프의 모든 정점에 대한 최단 거리 문제는 플로이드 - 워셜 알고리즘을 적용할 수 있겠다. 플로이드 - 워셜 알고리즘의 시간 복잡도는 O(N^3)이지만 이 문제에서 입력으로 주어지는 도시의 수 n은 최대 100으로 비교적 작은 값이기 때문에 시간 제한에 걸리지 않을 것이다. 

플로이드 - 워셜 알고리즘에 대해 정리한 이전 문제 풀이를 이 문제에도 적용이 가능하므로 관련 내용은 아래 링크를 참조하자.

 

[백준] 11403번 - 경로 찾기

 

 

 

다만, 문제 조건에 의하면 시작 도시와 도착 도시를 연결하는 도선이 하나가 아닐 수도 있다고 하였다. 따라서 도시간 버스 노선에 대한 입력을 받으면서 도시 쌍 (A, B)에 대한 버스 비용을 더 작은 비용으로 갱신하는 과정을 추가해주어야 한다. 

 

그 외 고려해야 할 부분은 사용할 변수의 자료형인데 모든 도시를 거치는 경로라고 해봐야 100,000 * 100 = 10,000,000이므로 Integer(int)을 사용해도 문제 없을 것이다. 

 

 

 

 

 

 

 

 

 

전체 코드

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

public class Main {
    
    static final int INF = Integer.MAX_VALUE;
    
    public static void main (String[] args) throws IOException {
        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = {};
        
        
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        
        
        int[][] path = new int[N+1][N+1];
        for (int[] city : path) Arrays.fill(city, INF);
        for (int i = 1; i <= N; i++) path[i][i] = 0;
        
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int a = Integer.parseInt(input[0]);
            int b = Integer.parseInt(input[1]);
            int c = Integer.parseInt(input[2]);
            
            // a -> b 간선 가중치(비용)가 더 작다면 갱신
            path[a][b] = Math.min(path[a][b], c);
        }
        
        
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                	// 도시 i에서 도시 k를 거쳐 도시 j에 도달할 수 있고, i -> j 비용이 기존 비용보다 더 작다면 갱신
                    if (path[i][k] != INF && path[k][j] != INF) 
                        path[i][j] = Math.min(path[i][j], path[i][k] + path[k][j]);
                }
            }
        }
        
        
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (path[i][j] == INF) 
                    sb.append(0 + " ");
                else 
                    sb.append(path[i][j] + " ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb);
        
        
        br.close();
    }
}