문제

문제 설명

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

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

---

Java

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));

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

        int[][] graph=new int[n][n];
        for(int[] i:graph)
            Arrays.fill(i, 10000000);

        for(int i=0; i<n; i++)
            graph[i][i]=0;

        for(int i=0; i<m; i++){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int x=Integer.parseInt(st.nextToken())-1;
            int y=Integer.parseInt(st.nextToken())-1;
            int cost=Integer.parseInt(st.nextToken());
            graph[x][y]=Math.min(graph[x][y], cost);
        }

        //1번 도시부터 n번 도시까지를 경유지로 했을 때 그래프 갱신 O(n^3)
        for(int k=0; k<n; k++)
            for(int start=0; start<n; start++)
                for(int end=0; end<n; end++)
                    graph[start][end]=Math.min(graph[start][end], graph[start][k]+graph[k][end]);

        for(int[] i:graph) {
            for (int j : i)
                System.out.print(((j==10000000)? 0: j) + " ");
            System.out.println();
        }
    }
}

---

해결 과정

1. 모든 도시간 구간에 대해서 줄어드는 경유지가 있다면 해당 경유지를 거쳐가도록 그래프를 수정한다. Floyd Warshall 방법으로 O(n^3)의 Time Complexity가 발생한다. 최대 N이 100이므로 100만번의 연산 정도면 된다.

2. 😁