[플로이드와샬] 백준 11404번 플로이드 (Java)

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

 

 

정말 기본 플로이드 와샬 알고리즘 그대로 사용하는 문제이다.

그래서 플로이드 와샬 알고리즘을 공부하면서 풀어보았다.

 

플로이드 와샬은 다대다 최단거리를 계산할 때 사용한다.

그만큼 속도가 느리지만, 모든 노드 사이의 최단 거리를 알아야 하는 문제에 사용한다.

 

그럼 어떻게 푸는지 한 번 살펴보자.

 

 

 

 

<1> 기본 세팅

N : 노드 개수

dp[N][N] : 모든 노드 사이의 최단 거리를 저장하는 배열

INF = 최대 거리(나는 N*maxlength로 두었다.)

 

<2> dp 초기화

자기 자신으로 가는 거리는 0 그대로 두고, 나머지는 INF로 설정한다.

예시)

 

<3> 간선 입력

간선을 입력받을 때, 기존 dp값과의 min값으로 저장합니다.

 

<4> 플로이드 와샬의 기본 구조

플로이드 와샬은 기본적으로 3중 for문을 사용합니다.

for (int k=0;k<N;k++) { // k : 경유지
    for (int i=0;i<N;i++) { // i : 시작점
        if (k==i) continue; // 경유지=시작점일 때 건너뛰어요.
        for (int j=0;j<N;j++) { // j : 도착점
            if (k==j || i==j) continue; // 경유지=도착점, 시작점=도착점일 때 건너뛰어요.
            dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]);
        }
    }
}

 

<5> 배열 출력

그리고 배열을 출력해주면 끝!!!

 

 

 

 

 

전체 코드를 보고 싶으신 분들은 아래를 눌러주세요!!

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // <1> 기본 세팅
        int INF = 100*100000;
        int N = Integer.parseInt(br.readLine()); // 노드 개수
        int M = Integer.parseInt(br.readLine()); // 간선 개수
        int[][] dp = new int[N][N];
        
        // <2> 배열 dp 초기화
        for (int i=0;i<N;i++) {
            for (int j=0;j<N;j++) {
                if (i==j) continue;
                dp[i][j] = INF;
            }
        }

        // <3> 간선 입력
        while (M-->0) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0])-1;
            int end = Integer.parseInt(input[1])-1;
            int cost = Integer.parseInt(input[2]);

            if (dp[start][end] > cost) dp[start][end] = cost;
        }

        // <4> 플로이드 와샬
        for (int k=0;k<N;k++) { // k : 경유지
            for (int i=0;i<N;i++) { // i : 시작점
                if (k==i) continue; // 경유지=시작점일 때 건너뛰어요.
                for (int j=0;j<N;j++) { // j : 도착점
                    if (k==j || i==j) continue; // 경유지=도착점, 시작점=도착점일 때 건너뛰어요.
                    dp[i][j] = Math.min(dp[i][j], dp[i][k]+dp[k][j]);
                }
            }
        }

        // <5> 배열 출력
        for (int i=0;i<N;i++) {
            for (int j=0;j<N;j++) {
                // INF라는 건 경로가 없다는 소리이므로 0을 출력해준다.
                if (dp[i][j] == INF) System.out.print("0 ");
                else System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
    }
}