[BOJ] 11404 - 플로이드 (Java)

알고리즘

• 그래프 이론
• 최단 경로
• 플로이드–워셜

1. 문제

2. Idea

• 플로이드 와샬 알고리즘 사용
  • 모든 정점에서 모든 정점으로의 최단거리

다익스트라 vs 플로이드 와샬

• 다익스트라: 하나의 정점 -> 모든 정점까지의 최단거리
• 플로이드 와샬: 모든 정점 -> 모든 정점까지의 최단거리

3. 풀이

3.1. 변수 선언 및 초기화

• int N: 도시의 수
• int M: 버스 노선의 수
• int[][] arr: 두 도시 간의 최단거리를 저장하는 2차원 배열

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][N + 1];

        // 초기값 설정
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = INF; // 두 도시 사이의 거리를 무한대로 설정 -> 경로가 없는 상태로 초기화

                if (i == j) {
                    arr[i][j] = 0; //자기 자신까지의 거리는 항상 0
                }
            }
        }

3.2. 배열 저장

• 두 도시 사이의 최소 거리 입력 저장
• 동일한 출발지와 도착지에 대해 여러 입력값이 있을 때, 가장 작은 비용만을 저장

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

            // 출발 도시와 도착 도시가 같지만 시간이 다른 입력값이 들어온 경우 작은 값을 선택
            arr[a][b] = Math.min(arr[a][b], c); // 현재 도시 a -> 도시 b 최소 비용
        }

3.3. 최단경로 업데이트

• k: 정점(경유점), i: 출발점, j: 도착점

// 플로이드 와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // 최단경로 초기화
                    // 경로가 존재하는지 확인
                    // i->k->j로 가는 경로가 배열 내 최단경로보다 짧은지 확인
                    if (arr[i][k] != INF && arr[k][j] != INF && arr[i][j] > arr[i][k] + arr[k][j]) {
                    // 최단거리 i->k->j 업데이트
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

3.4. 결과 출력

 for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // 갈 수 없는 곳(경로가 없는 곳)은 0으로 초기화
                if (arr[i][j] == INF) {
                    arr[i][j] = 0;
                }

                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }

4. 전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final int INF = 1000000000;  // 충분히 큰 값으로 설정

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());
        int[][] arr = new int[N + 1][N + 1];

        // 초기값 설정
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                arr[i][j] = INF;

                if (i == j) {
                    arr[i][j] = 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());

            // 출발 도시와 도착 도시가 같지만 시간이 다른 입력값이 들어온 경우 작은 값을 선택
            arr[a][b] = Math.min(arr[a][b], c);
        }

        // 플로이드 와샬 알고리즘
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    // 최단경로 초기화
                    if (arr[i][k] != INF && arr[k][j] != INF && arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                // 갈 수 없는 곳은 0으로 초기화
                if (arr[i][j] == INF) {
                    arr[i][j] = 0;
                }

                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
    }
}