[알고리즘] 백준 11404 플로이드 -플로이드 워셜- 자바

 

www.acmicpc.net/problem/11404

11404번: 플로이드

 

 

 

 

알고리즘 플로이드 워셜 유형을 풀어봤습니다.

chanhuiseok.github.io/posts/algo-50/

알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

blog.naver.com/ndb796/221234427842

24. 플로이드 와샬(Floyd Warshall) 알고리즘

알고리즘 시간에 배우긴 했었지만 너무 오랜만에 보기도 했고 알고리즘 공부때 처음 푸는 유형이라 개념을 다시 보고 풀었습니다. 위 나동빈 님께서 잘 설명해놓으신 것 같습니다.

 

간단히 설명하면 다익스트라는 하나의 정점에서 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이라면 , 플로이드-워셜 알고리즘은 모든 정점에서 정점간의 모든 노드 간 최단 경로를 구할 수 있습니다. 

 

또한 정점을 3중 for문을 돌기 때문에 O(V^3) 의 시간복잡도를 가지고 간선들의 정보를 V∗V 크기의 인접행렬에 담았기 때문에 O(V^2)의 공간 복잡도를가집니다.

시간복잡도면에서 정점의 개수가 적당하고 간선의 개수가 많을 경우 유리한 알고리즘인 것 같습니다.

 

 

풀이 시 주의사항은 보통 무한대를 뜻하는 INF를 최소신장트리처럼 Integer.MAX_VALUE로 하면 안됩니다. 나중에 가중치 합해줄때 무한대+자연수는 음수가 되기 때문입니다. 

풀이코드는 주석과 함께 이해하기 쉬우므로 설명은 생략하도록 하겠습니다.

 

[Java]

import java.util.Scanner;

class Main {
    private static int n; // n개의 도시
    private static int m; //m개의 버스
    private static int[][] distance; // 최소비용
    private static int INF = 1000000000; //Integer.MAX_VALUE 로 하면 안된다. 나중에 더해줘야하는데 그럼 수가 초과해서 마이너스가된다. (주의)

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        distance = new int[n + 1][n + 1];

        //초기화
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) distance[i][j] = 0;
                else distance[i][j] = INF;
            }
        }
        for (int i = 0; i < m; i++) {
            int start = sc.nextInt();
            int end = sc.nextInt();
            int weight = sc.nextInt();
            distance[start][end] = Math.min(distance[start][end], weight);
        }

        //플로이드 워셜 알고리즘
        floyd();

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

    private static void floyd() {
        for (int k = 1; k <= n; k++) { //거쳐가는 중간 지점 노드
            for (int i = 1; i <= n; i++) { //시작 노드
                for (int j = 1; j <= n; j++) { //도착 노드
                    distance[i][j] = Math.min(distance[i][k] + distance[k][j], distance[i][j]); //최단경로 초기화
                }
            }
        }
    }
}

 

 

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!