백준 11404번 : 플로이드

플로이드워셜 알고리즘을 공부하기 위해 해당 알고리즘의 기본 문제를 풀어봤다.

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보다 작거나 같은 자연수이다.

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

 

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[][] arr = new int[N+1][N+1];
        int INF = 9900001;
        // INF 값을 100001로 잡은 경우
        // A---100000---B---1---C일 경우 100001이 되어 마지막에 0으로 처리하게 돼서 안됨
        // INF값을 잡을 때는 최악의 상황에서 +1해주는게 좋음
        // 본 문제의 경우 100000 * (100-1) + 1
        // 근데 귀찮으니까 Integer.MaxValue

        //초기배열 INF로 초기화
        for(int i=0; i<=N; i++) {
            for(int j=0; j<=N; j++) {
                arr[i][j] = INF;
                if(i==j) arr[i][j] = 0;
            }
        }

        //input
        StringTokenizer st;
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            //같은 경로의 버스 중 요금이 더 싼 경우가 있음
            arr[start][end] = Math.min(cost, arr[start][end]);
        }

        //floyd_warshall
        for(int k=1; k<=N; k++) {
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        //output
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(arr[i][j]==INF) arr[i][j] = 0;  //INF값은 경로가 없는 곳 이기 떄문에 0으로 바꿔줌
                sb.append(arr[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

    }//end main
}

 

해당문제에서 주의해야할 점은 같은 경로라 하더라도 다른 버스의 요금이 존재하기 때문에 인풋을 받을 때 기존 경로의 비용보다 더 싼 경우에 바꿔줄 수 있도록 했다.

 

그리고 플로이드 워셜 알고리즘 적용을 위해 INF 값으로 초기화를 하는 과정에서 INF값을 100,001로 했었다.

최대 비용이 100,000 이라고 해서 이렇게 설정을 했었는데, 잘못된 생각이었다.

A---100,000---B---1---C
위와 같이 간선이 존재하는 경우, A에서C까지의 비용은 100,001이 된다. 하지만 INF를 100,001로 줬기 때문에 INF값과 똑같아 지면서 없는 경로라고 체크가 된다.

 

그렇기에 INF값을 설정할 때는 최악의 상황에서 +1 해주는 것이 좋다.

본 문제의 경우 100,000 * (100-1) +1 = 9,900,001