백준 – 1753 최단 경로 – Java + Dijkstra

백준 최단 경로 문제를 해결했습니다.

대표적인 최단경로 알고리즘이 3가지 있는데 어려워 보여서 ​​계속 옮겼는데 이번 기회에 공부를 하게 되었고 알면 유용하고 생각보다 어렵지 않은 알고리즘이었습니다.

3개의 알고리즘을 문제에 바로 적용하여 정리한 것으로, 이 문제는 Dijkstra가 적용한 문제이다.

• 최단 경로 솔루션 알고리즘
  • 다익스트라
  • 벨만 포드
  • 플로이드 워샬

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

루트 1753: 최단 경로

모서리의 수 V와 가장자리의 수 E는 첫 번째 줄에 제공됩니다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점이 1에서 V까지 번호가 매겨져 있다고 가정합니다. 두 번째 줄에는 시작 노드 번호 K(1 ≤ K ≤ V)가 포함됩니다.

www.acmicpc.net

---

문제 설명

• 유방향 그래프가 주어지면 시작점에서 다른 모든 정점까지의 최단 경로를 찾는 프로그램
• 모서리의 가중치는 10(양수) 이하의 자연수입니다.
• 시작점에서 모든 노드까지의 최단 경로만 출력
• 20,000개 노드, 300,000개 에지

제한으로 인해 Floyd Warhall을 적용할 수 없음(시간 복잡도 O(v^3))

따라서 Dijkstra와 Bellman-Ford 알고리즘으로 풀 수 있는 문제이지만,

Bellman-Ford 알고리즘은 음의 가중치와 음의 주기를 구별하는 더 나은 알고리즘이므로 Dijkstra를 적용하여 해결할 수 있습니다.

게다가 에지의 수가 300,000개로 매우 많기 때문에 인접 리스트로 그래프를 구현하면 해결된다.

---

다익스트라 알고리즘

• 차트에서 최단 거리를 찾는 알고리즘
• 시작 노드와 모든 노드 사이의 최단 거리 찾기
• 간선(가중치)은 모두 양수입니다.
• 시간 복잡도 O(ElogV)

그래프가 다음과 같이 주어진다고 가정합니다. (문제에서는 유향 그래프이지만 예제에서는 무향 그래프입니다.)

지금은 거리 배열을 무시합시다.

Dijkstra의 알고리즘을 구현하려면

1. 그래프를 인접 목록으로 구현합니다. (노드 번호, 가중치)

• 노드 1 – (2, 5), (4, 9), (5, 1)
• 노드 2 – (1, 5), (3, 2)
• 매듭 3 – (2, 2), (4, 6)
• 매듭 4 – (1, 9), (3, 6), (5, 2)
• 노드 5 – (1, 1), (4, 2)

2. 가장 짧은 어레이 간격을 만듭니다. (시작점의 가중치는 0으로 초기화)

3. 최단 경로 업데이트(중요)

1. 값이 가장 작은 노드 선택
2. 선택한 노드에 연결된 노드의 값을 기준으로 다른 노드의 값을 업데이트(최단 거리 배열 업데이트)

가장 짧은 어레이 업데이트 프로세스

D 배열에서 가장 짧은 거리에 있는 노드를 선택하고 연결된 노드의 최단 경로를 업데이트합니다.

• 첫 번째(시작) 노드의 값이 최소이므로 첫 번째 노드에 연결된 노드를 찾습니다.

노드 2의 값과 d(2) > d(1) + w인 경우 d(2) 업데이트

다른 노드에 대해 반복

• 동일한 노드를 반복할 수 없기 때문에(시간 복잡도) 노드 1 방문 여부를 true로 설정합니다.

---

• 이미 방문한 노드 1이 없는 경우 경로가 가장 짧은 노드 선택 -> 노드 5 선택
• 방문 처리 및 유사하게 5번에 연결된 노드 중 최단 경로 업데이트
• d(4) < d(5) + 승? d(5)+w : d(4)

---

• 다음 4개 노드 방문
• 업데이트하려면
• d(3) < d(4) + 승?

---

• 다음 2회 방문
• 업데이트하려면

---

• 다음 3회 방문
• 업데이트(없음)

---

4. 시작점에서 각 노드까지의 최단 경로 배열이 완성됩니다.

의미

• 시작점(1)에서 노드 i까지의 최단 경로를 의미합니다.
• 시작점이 무엇인지에 따라 완성되는 범위 배열이 달라집니다.

---

문제 해결 코드

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() d, visited;
    public static void main(String() args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int v = Integer.parseInt(st.nextToken()), e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());
        for(int i=0; i<=v; i++){
            graph.add(new ArrayList<>());
        }
        for(int i=0; i<e; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken()), n2 = Integer.parseInt(st.nextToken()), w = Integer.parseInt(st.nextToken());
            graph.get(n1).add(new Node(n2, w));
        }
        d = new int(v+1);
        visited = new int(v+1);
        Arrays.fill(d, Integer.MAX_VALUE);
        d(k) = 0;    // 시작 노드
        dijkstra(k);
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<=v; i++){
            if(d(i) == Integer.MAX_VALUE) sb.append("INF\n");
            else sb.append(d(i)+"\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(d(node.num) > d(n.num) + node.w) d(node.num) = d(n.num) + node.w;
                // 업데이트 된 최소 비용으로 다음 노드로 간다
                queue.offer(new Node(node.num, d(node.num)));
            }
        }
    }
}

• edge가 많기 때문에 adjacency list로 구현한다.
• 가중치에 대한 Node 클래스 객체 만들기
• PriorityQueue를 사용하여 현재 순서에서 가장 짧은 경로인 노드를 반복하여 비교기 람다 식 정의
• 방문한 노드는 방문한 위치에서 제외됩니다.

---

Dijkstra 응용 문제 자체는 알고리즘만 이해하면 쉬워 보입니다.

Bellman-Ford 알고리즘으로 문제를 해결하고 해결해야 할 몇 가지 문제가 아직 남아 있습니다.