BOJ G4 11404 플로이드 JAVA

11404번: 플로이드

---

문제 읽기

문제는 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제이다. 근데 알고리즘을 어떤 걸 써야 하는지는 문제 이름에서 스포를 당하긴 했지만.. 플로이드 워샬 알고리즘이 잘 기억이 나지 않아서 처음엔 그냥 다익스트라를 N번 돌렸다.

 

그래도 플로이드 워샬 알고리즘도 정리할 겸 공부해서 다시 풀어보았다.

---

문제 풀기

다음과 같이 다익스트라와 플로이드 워샬로 풀었다.

 

다익스트라

모든 정점에서 다른 모든 정점까지의 최단 거리니까 다음 코드와 같이 모든 노드를 출발점으로 하여 다익스트라를 N번 돌리면 된다.

 

다익스트라에 관한 자세한 설명은 다음 포스팅을 참고하면 된다.

다익스트라, Dijkstra Algorithm

package ps.ㄱSolving;

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

public class BOJ_G4_11404_플로이드_ver다익스트라 {
    static class Node{
        int no, cost;
        public Node(int no, int cost){
            this.no = no;
            this.cost = cost;
        }
    }
    static int N, M;
    static List<List<Node>> graph;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        M = Integer.parseInt(in.readLine());
        graph = new ArrayList<>();
        for (int i = 0; i < N+1; i++){
            graph.add(new ArrayList<>());
        }

        while(M-- > 0){
            StringTokenizer st = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph.get(a).add(new Node(b, cost));
        }

        int[][] dist = new int[N+1][N+1];
        for (int i = 0; i < N+1; i++){
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        for (int i = 1; i < N+1; i++){
            dijkstra(i, dist[i]);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < N+1; i++){
            for (int j = 1; j < N+1; j++){
                sb.append((dist[i][j] == Integer.MAX_VALUE)? 0 : dist[i][j]).append(" ");
            }
            sb.append("\\n");
        }
        System.out.println(sb);
    }

    private static void dijkstra(int start, int[] dist) {
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.cost - o2.cost;
            }
        });
        pq.offer(new Node(start, 0));
        dist[start] = 0;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            for (Node adj : graph.get(cur.no)){
                if (dist[adj.no] > dist[cur.no] + adj.cost){
                    dist[adj.no] = dist[cur.no] + adj.cost;
                    pq.offer(new Node(adj.no, dist[adj.no]));
                }
            }
        }
    }
}

 

플로이드 워샬

 

일단 플로이드 워샬 알고리즘이 잘 기억나지 않아서 정리했다.

Floyd-Warshall, 플로이드 워샬 알고리즘

간단하게만 정리하자면, 모든 정점에서 다른 모든 정점까지의 최단 거리를 구할 때 사용하는 알고리즘으로, 음의 사이클만 없으면 음수의 가중치가 있어도 동작하는 알고리즘이다. 시간복잡도는 N^3으로, 현재 문제에서 충분한 시간이다.(N = 100)

 

그 다음 문제를 풀었다. 알고리즘만 적용하면 바로 풀리는 문제였다.

 

좀 더 자세한 설명은 위 포스팅에서 확인할 수 있다.

package ps.ㄱSolving;

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

public class BOJ_G4_11404_플로이드 {
    static int[][] graph;
    static int INF = Integer.MAX_VALUE / 2 -1;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int M = Integer.parseInt(in.readLine());
        graph = new int[N+1][N+1];
        for (int i = 0; i < N+1; i++){
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0; //자기자신은 0
        }
        while(M -- > 0){
            StringTokenizer st = new StringTokenizer(in.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[a][b] = Math.min(graph[a][b], cost); //노선이 여러개일 수 있다고 했으니까
        }

        //floyd-warshall
        //경유지
        for (int k = 1; k <= N; k++){
            for (int i = 0; i <= N; i++){
                for (int j = 0; j <= N; j++){
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= N; j++){
                sb.append((graph[i][j] == INF)? 0 : graph[i][j]).append(" ");
            }
            sb.append("\\n");
        }
        System.out.println(sb);
    }
}

 

아래가 다익스트라이고 위가 플로이드 워샬이다.

두 방법으로 모두 해봤더니 플로이드 워샬의 메모리와 수행 시간이 엄청 짧게 나왔다. 아무래도 N(=V)이 100으로 작고, m(=E)은 100000로 좀크다 보니 다익스트라 N번 보다는 플로이드 워샬이 훨씬 효율적인 것 같다.

 

참고로 다익스트라의 시간 복잡도는 O(ElogV)이고, 플로이드 워샬의 시간 복잡도는 O(V^3)이다.