백준 - 11404 플로이드 - Java + 플로이드 워셜

백준 플로이드 문제를 풀어보았다.

이번 문제에서는 노드의 수가 100개로 적은 수이고, 모든 노드를 시작점으로 했을 때 최소 경로를 모두 출력하기 때문에 

플로이드 워셜 알고리즘을 이용해 풀면 간단하게 풀 수 있는 문제이다.

추가로, 다익스트라를 각 노드를 시작점으로 실행하여 돌면 같은 결과이며 차이가 얼마나 나는지 궁금해 테스트해보았다

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

11404번: 플로이드

---

문제 설명

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

• n개 도시가 있고, 한 도시에서 출발하여 다른 도시에 도착하는 버스 m개
• 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다 (최단 경로이기 때문에 작은 값 하나만 있으면 됨)
• 도시 i에서 j로 가는데 필요한 최소비용을 모두 출력, 갈 수 없으면 0을 출력

제한 조건에서 도시의 수가 100개로 적고, 버스 노선 에지의 수가 10만 개로 많다. 또한 모든 시작 도시에서의 최단 경로를 출력해야 하므로 인접 행렬로 플로이드 워셜 알고리즘을 적용해 풀 수 있다.

---

플로이드 워셜 알고리즘

• 모든 노드 간에 최단 경로 탐색
• 음수 가중치 에지가 있어도 수행 가능
• 동적 계획법의 원리를 이용해 알고리즘 접근
  • i에서 j까지의 최단경로는 i에서 k까지의 최단경로 + k에서 j까지 최단경로임을 이용
• 시간복잡도 O(V^3)

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

1. 인접 행렬로 그래프를 구현한다. (i == j인 경우는 0으로 초기화)

map[i][j] = w, i에서 j까지의 최단 경로 비용 w

 

2. 거쳐가는 노드를 k로 설정하고 (처음에 1로 했다고 가정)

 

3. i 노드에서 j노드를 갈 때 k를 거쳐가는 최단 경로를 업데이트한다.

map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j])

점화식이 위와 같기 때문에 평소처럼 초기화를 Integer.MAX_VALUE를 이용하면 오버플로우가 발생하니 이를 주의하도록 한다

---

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

인접 행렬을 초기화

0	5	INF	9	1
5	0	2	INF	INF
INF	2	0	7	INF
9	INF	7	0	2
1	INF	INF	2	0

 

---

1번 노드를 중간 노드로 설정하고 업데이트를 진행한다

map[i][j] = Math.min(map[i][j], map[i][1] + map[1][j])

 

map[2][4] = Math.min(map[i][j], map[2][1] + map[1][4]) = 14로 갈 수 있게 되며 최소 비용으로 업데이트됨

0	5	INF	9	1
5	0	2	14	6
INF	2	0	7	INF
9	14	7	0	2
1	6	INF	2	0

 

이와 같은 구하려는 경로 i = 1 ~ n, j = 1 ~ n에 대하여 중간노드가 1 ~ n에 대해 최단 경로를 업데이트할 수 있도록 반복

아무래도 코드가 더 이해하기 쉬울 것 같고 생각보다 코드는 간단하다

// 플로이드 워셜 알고리즘
for(int k=1; k<=n; k++){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
        }
    }
}

---

풀이 코드

import java.util.*;
import java.io.*;

class Main{
    public static int[][] map;
    public static final int INF = 10000001;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        map = new int[n+1][n+1];
        // 경로 값 초기화
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                map[i][j] = i == j ? 0 : INF;
            }
        }
        int m = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            map[s][e] = Math.min(map[s][e], w); // 같은 도시를 연결하는 노선이 하나가 아닐 수 있다
        }
        // 플로이드 워셜 알고리즘
        for(int k=1; k<=n; k++){
            for(int i=1; i<=n; i++){
                for(int j=1; j<=n; j++){
                    map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(map[i][j] == INF) sb.append("0 ");
                else sb.append(map[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.print(sb);
        br.close();
    }

}

• INF 값은 최대 비용이 10만이고 노드가 100개까지이므로 10000001로 설정
• i == j인 경우 시작과 끝이 자기 자신인 경우에는 0으로 초기화
• 같은 도시를 연결하는 노선이 한 개가 아닐 수 있기 때문에 최소 값으로 초기화할 수 있어야 한다

---

다익스트라 풀이 코드 (시간 초과)

import java.util.*;
import java.io.*;

class Main{
    static class Node{
        int num, w;
        public Node(int num, int w){
            this.num = num; this.w = w;
        }
    }
    public static List<ArrayList<Node>> graph = new ArrayList<>();
    public static int[] distance, visited;
    public static final int INF = 100000001;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        int m = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            graph.get(s).add(new Node(e, w));
        }
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=n; i++){
            distance = new int[n+1];
            visited = new int[n+1];
            Arrays.fill(distance, INF);
            distance[i] = 0;
            dijkstra(i);
            for(int j=1; j<=n; j++){
                if (distance[j] == INF) {
                    sb.append("0 ");
                } else {
                    sb.append(distance[j] + " ");
                }
            }
            sb.append("\n");
        }
        System.out.print(sb);
        br.close();
    }
    public static void dijkstra(int start){
        Queue<Node> queue = new PriorityQueue<>((n1, n2) -> n1.w - n2.w);
        queue.offer(new Node(start, 0));
        while(!queue.isEmpty()){
            Node n = queue.poll();
            if(visited[n.num] == 1) continue;
            visited[n.num] = 1;
            for(Node node : graph.get(n.num)){
                if(distance[node.num] > distance[n.num] + node.w){
                    distance[node.num] = distance[n.num] + node.w;
                }
                queue.offer(new Node(node.num, distance[node.num]));
            }
        }
    }

}

결과는 시간 초과이다.

하나의 정점에 대해서 최단경로를 정렬하면 시간복잡도가 O(ElogN)이었다면 모든 정점에 대해서 N번 반복해야 하므로

O(ENLogN)이 됨 수치적으로 100^3보다 100000 * 100 * log 100이 더 크고 PrioirytyQueue에서 정렬하는 부분도 시간이 더 들 것이다.

 

따라서 모든 정점에 대해 모든 최단 경로를 출력할 때는 플로이드 워셜 알고리즘을 적용하는 게 다익스트라 방식보다 빠르다라