[백준] 11404 : 플로이드

문제 출처: 11404번: 플로이드 (acmicpc.net)

소요 시간: 시도(1h 30m 이상)

---

문제

---

시도

 

문제 분류는 '최단 경로'이지만 다른 문제에서 BFS만으로 풀 수 있었기에 BFS로 풀어보려고 했는데, 갈 수 없는 지점을 찾기 위한 과정을 찾는 방법을 알아내지 못해 결국 실패했다.

 

---

풀이

 

이 문제는 플로이드-와샬 알고리즘을 사용하는 기초 문제로, 주의해야 했던 점은 도시에 대한 중복 접근이 가능하기 때문에 기존 BFS처럼 방문 여부 집합인 visited를 쓰지 않는다는 것이었다. 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
    static final int INF = 987654321;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }
 
        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;
                }
 
                sb.append(arr[i][j] + " ");
            }
            sb.append("\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

사실 풀이를 보고 가장 어이없던 점은 시간 복잡도가 O(n^3)인 알고리즘을 통해 풀리는 문제였다는 것이다.

 

그래서 개념을 좀 더 살펴보니 그래프의 크기가 충분히 작아 O(n^3)를 적용해도 되는 문제에 대해서만 적용할 수 있었다.

 

 

 

풀이 참조 : [BOJ] 백준 11404번 : 플로이드 (JAVA) (tistory.com)

개념 참조 : https://blog.naver.com/ndb796/221234427842

---

알게 된 점

 

알고리즘의 세계는 넓구나...