백준 11404 플로이드 - JAVA

11404 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

<다익스트라 알고리즘>

import java.util.*;
import java.io.*;
 
class Node implements Comparable<Node> {
    int target;
    int weight;
    
    Node(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
    @Override
    public int compareTo(Node n) {
        return weight - n.weight;
    }
}
 
public class Main {
    static int n;
    static List<List<Node>> list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        } 
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(a).add(new Node(b, c));
        } 
        StringBuilder sb = new StringBuilder();
        int[] result = new int[n+1];
        for (int i = 1; i <= n; i++) {
            result = dijkstra(i);
            for (int j = 1; j < n+1; j++) {
                if (result[j] != Integer.MAX_VALUE) {
                    sb.append(result[j]).append(" ");
                } else {
                    sb.append(0).append(" ");
                }
            } 
            sb.append("\n");
        } 
        bw.write(sb.toString());
        bw.flush();
    }
    private static int[] dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        pq.offer(new Node(start, 0));
        while(!pq.isEmpty()) {
            Node current = pq.poll();
            int currentNode = current.target;
            int currentWeight = current.weight;
            if (dist[currentNode] < currentWeight) {
                continue;
            } 
            for (Node next : list.get(current.target)) {
                int nextNode = next.target;
                int nextWeight = next.weight;
                if (dist[nextNode] > currentWeight + nextWeight) {
                    dist[nextNode] = currentWeight + nextWeight;
                    pq.offer(new Node(nextNode, dist[nextNode]));
                } 
            }
        }
        return dist;
    }
}

---

<플로이드 알고리즘>

import java.util.*;
import java.io.*;
 
public class Main {
    static int n;
    static long[][] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        
        dist = new long[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            } 
        } 
        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            dist[a][b] = Math.min(dist[a][b], c);
        } 
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                } 
            } 
        } 
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dist[i][j] < Integer.MAX_VALUE) {
                    sb.append(dist[i][j]).append(" ");
                } else {
                    sb.append(0).append(" ");
                }
            } 
            sb.append("\n");
        } 
        bw.write(sb.toString());
        bw.flush();
    }
}

 

 

알고리즘 설명

---

이 문제는 다익스트라 알고리즘과 플로이드-워셜 알고리즘으로 해결이 가능합니다. 문제의 제목에서 볼수있듯이, 다익스트라 알고리즘이 출발노드로부터 도착노드까지의 최단 거리를 구한다면, 플로이드-워셜 알고리즘은 동적계획법 알고리즘 중 하나로, 그래프내의 모든 노드간의 최단거리를 계산할 때 사용됩니다. 플로이드-워셜 알고리즘이 익숙하지 않으신 분들은 아래의 링크를 참고하시길 바랍니다. 공식 비슷한 코드가 있는 알고리즘이어서 이해와 적용이 어렵지 않다고 생각합니다. 아래 이미지는 다익스트라 알고리즘으로 하나의 노드를 기준으로 모든 경로를 구했을 때의 결과와, 플로이드 알고리즘을 사용하여 구했을 때의 결과입니다.

위부터 차례대로 플로이드, 다익스트라

 

- 참고 -

https://namu.wiki/w/플로이드-워셜%20알고리즘

플로이드-워셜 알고리즘

 

 

코드 해석

---

플로이드 코드를 기준으로 설명드리겠습니다. 두 도시간의 최단거리를 저장할 dist 2차원 배열을 선언합니다. 출발과 도착지점이 같은 곳은 0으로 설정하고, 나머지는 int 자료형의 최댓값을 설정합니다. 이 후, a -> b로 가는 비용 c가 가장 작은 거리일 경우에 dist[a][b]에 저장하고, 모든 정점 쌍 (i, j)에 대해 중간 노드(k)를 거쳐서 가는 경로의 최단 거리 계산합니다. dist[i][j]가 int자료형의 최댓값보다 큰 경우에는 도달할 수 없는 노드로 취급하고 0을 설정합니다. 이후 dist의 모든 원소를 StringBuilder sb에 형식에 맞게 입력하고, sb를 출력합니다.