[백준 11404] - [플로이드 와샬] - 플로이드 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/11404

---

이 문제는 새로 접하는 알고리즘인 플로이드 와샬(Floyd Warshall) 알고리즘이다. 

최단 경로를 구하는 알고리즘이다. 

2차원 배열로 존재하면서 기준점 K를 두고 I에서 J 까지 가는 거리와 I에서 K 까지 갔다가 K에서 J 까지 가는 거리 두가지를 비교하여 최소 값을 최단 거리로 구하면 된다. 

문제에서 주어진 예제 입력으로 플로이드 와샬 알고리즘을 공부해보자.

이 문제에서 요구하는 답은  N 개의 도시가 존재하고 1 부터 N까지의 도시각 각각의 도시에 갈 수 있는 최소 비용이다.

N x N 의 2차원 배열로 존재하고 각 도시의 도달할 수 있는 최소비용이 저장되면 된다.

비용을 저장하는 배열에는 무한대의 값으로 초기화 해주어야 한다.

무한대로 지정해주는 이유는 이후에 입력 받는 버스정보에서 A 도시에서 B 도시로 갈 수 있는 버스 정보를 받지 못할 수 있기 때문이다. 

그리고 A에서 A 도시 로 가는 비용은 당연히 0이기때문에 이부분도 처리를 해주어야 한다. 

for(int i=1; i <= cityCount; i++) { for(int j=1; j <= cityCount; j++) { if(i == j) continue; distance[i][j] = INF; } }

입력에서는  버스 정보에 대한 입력이 주어지는데 입력값 a, b, c 에서 a 는 출발 도시 , b 는 도착 도시 c 는 비용 을 나타낸다.

그럼 버스 정보를 입력받으면서 2차원 배열에 1차적으로 비용을 입력 할 수가 있다. 

while(busCount-- > 0) { st = new StringTokenizer(br.readLine()); int start = Integer.parseInt(st.nextToken()); int end = Integer.parseInt(st.nextToken()); int time = Integer.parseInt(st.nextToken()); distance[start][end] = Math.min(distance[start][end], time); }

예제 입력받은 버스정보를 토대로  1차 최소 비용 테이블은 아래와 같이 완성된다.

0	2	3	1	10
INF	0	INF	2	INF
8	INF	0	1	1
INF	INF	INF	0	3
7	4	INF	INF	0

플로이드 와샬로 이제 최소 비용을 구해보자.

플로이드 와샬에서 중요한거는 거쳐가는 노드 이다.

모든 노드들을 한번씩 거쳐가는 기준점 K로 잡고 시작점 A에서 B로 간다고 했을때 

A에서 B로 가는 기존의 비용과 A 에서 K로 갔다가 K에서 B로 가는 비용을 비교하여 더 작은값을 A에서 B로 가는 최소 비용으로 변경해주면 된다.

public static void floydWarshall() { // 기준이 되는 거쳐가는 노드 K for(int k = 1; k <= cityCount; k++) { // 출발하는 노드 i for(int i=1; i <= cityCount; i++) { // 도착하는 노드 j for(int j=1; j <= cityCount; j++) { //i에서 k를 거쳤다가 k에서 j 까지 가는 거리와 i에서 j 까지 가는 거리를 비교해서 작은 값이 최소거리이다. distance[i][j] = Math.min(distance[i][k] + distance[k][j], distance[i][j]); } } } }

각 도시들을 전부 거쳐가는 노드로 기준을 잡고 1번 도시부터 N 도시까지 의 최소 비용을 구하면 된다.

이렇게 하더라도 끝까지 접근할 수 없는 도시가 존재할 수 있다. 

그런 경우에는 출력할때 꼭 무제한일 경우 0을 출력하도록 해주어야 한다.

public static void print() { StringBuilder sb = new StringBuilder(); for(int i=1; i <= cityCount; i++) { for(int j=1; j <= cityCount; j++) { if(distance[i][j] >= INF) sb.append("0 "); else sb.append(distance[i][j] + " "); } sb.append("\n"); } System.out.println(sb.toString()); }

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    //플로이드 와샬 알고리즘 문제.
    
    public static int cityCount;
    public static int[][] distance;
    public static final int INF = 1000000000;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        cityCount = Integer.parseInt(br.readLine());
        
        int busCount = Integer.parseInt(br.readLine());
        
        distance = new int[cityCount+1][cityCount+1];
        
        for(int i=1; i <= cityCount; i++) {
            for(int j=1; j <= cityCount; j++) {
                if(i == j) continue;
                distance[i][j] = INF;
            }
        }
        
        while(busCount-- > 0) {
            st = new StringTokenizer(br.readLine());
            
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            
            distance[start][end] = Math.min(distance[start][end], time);    
        }
 
        floydWarshall();
        print();
    }
    
    public static void floydWarshall() {
        // 기준이 되는 거쳐가는 노드 K
        for(int k = 1; k <= cityCount; k++) {
            // 출발하는 노드 i
            for(int i=1; i <= cityCount; i++) {
                // 도착하는 노드 j
                for(int j=1; j <= cityCount; j++) {
                    //i에서 k를 거쳤다가 k에서 j 까지 가는 거리와 i에서 j 까지 가는 거리를 비교해서 작은 값이 최소거리이다.
                    distance[i][j] = Math.min(distance[i][k] + distance[k][j], distance[i][j]);
                }
            }
        }
    }
    
    public static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i=1; i <= cityCount; i++) {
            for(int j=1; j <= cityCount; j++) {
                if(distance[i][j] >= INF) sb.append("0 ");
                else sb.append(distance[i][j] + " ");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
}