[백준 11404번] 플로이드 - JAVA

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

11404번: 플로이드

풀이

사용한 알고리즘 : 플로이드 워셜 알고리즘(Floyd Warshall)

 

풀이전략

전형적인 플로이드 워셜 알고리즘을 사용한 문제이다.

플로이드 워셜은 A에서 B로 가는 거리를 D(AB)라고 할 때,

다른 노드 K를 지나쳐 가는 것과 현재 거리를 비교하여 더 짧은 거리를 D(AB)에 저장시키는 알고리즘이다.

 

예로 D(AB) = Math.min(D(AB),D(AK)+D(KB))처럼 특정 노드 K를 방문할 때,

더 최단거리가 있다면 그 값을 저장한다.

 

3중 for문을 쓰며 알고리즘 자체는 간단하나

각 반복문에서 쓰이는 변수가 그래프의 어떤 위치에 들어가야하는지 주의해야한다.

 

static void floydWarshall(){
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            for(int k=0;k<n;++k)
                graph[j][k]=Math.min(graph[j][k],graph[j][i]+graph[i][k]);
}

최외각 for문에서 정의된 변수 i가 K의 역할을 수행하고 있다.

이유는 모든 A, B 경우의 수에서 K라는 노드를 방문했을 경우에 더 짧은 거리가 있는지 파악하기 위해서다.

 

또 플로이드 워셜 알고리즘과 별개로 문제를 풀 때 주의할 점이 하나 더 있다.

위 문제의 입력 예제를 보면 출발 도시와 도착 도시가 같은 버스 노선이 있다.

(1 4 1)과 (1 4 2)로 우리는 최단 거리를 구하고 있으므로 둘 중 거리가 짧은 (1 4 1)을 선택해야 문제를 올바르게 해결할 수 있다.

 

제출코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import static java.lang.String.valueOf;

public class Main {

    static int[][] graph=new int[100][100];
    static final int INF = 987654321;
    static int n,m;

    static void floydWarshall(){
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                for(int k=0;k<n;++k)
                    graph[j][k]=Math.min(graph[j][k],graph[j][i]+graph[i][k]);
    }
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

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

        for(int i=0;i<n;++i) Arrays.fill(graph[i],INF);
        for(int i=0;i<n;++i) graph[i][i]=0;

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

        floydWarshall();

        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                if(graph[i][j]==INF) sb.append(0).append(' ');
                else sb.append(graph[i][j]).append(' ');
            }
            sb.append("\n");
        }
        bw.write(valueOf(sb));
        bw.flush();
        bw.close();
    }
}