다익스트라 (Dikjstra) (with. 백준 1916)

Notion - 다익스트라

 

이번에는 다익스트라에 대해 정리하고, 문제를 기준으로 이해해보자.

 

https://www.acmicpc.net/problem/1916 - 최소비용 구하기 / Gold 5

 

위 문제의 예제인 아래 입력을 기준으로 설명해보도록 하겠다.

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

다익스트라 알고리즘?

다익스트라는 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다.

다익스트라는 2중 for문을 이용한 방법, 우선순위 큐를 이용한 탐색으로 구현 방법이 나뉜다.

그럼 이번에도 그림으로 표현해보도록 하겠다.

 

이전 글인 플로이드 워셜과 유사하게 접근이 가능하다.

INF를 사용하지만 이번에는 시작 지점만을 위한 가중치 배열인 dist를 따로 선언하여 사용한다.

처음에는 dist 배열 내에서 시작 지점인 자신을 제외한 모든 노드를 향한 가중치를 INF로 두고 업데이트해나가며 다른 모든 노드까지의 최단거리를 구해낼 수 있다.

구현 - 우선 순위 큐

먼저 위에서 그림으로 표현한 인접리스트 방식으로 설명하겠다.

private static class Node implements Comparable<Node>{ // Comparable 구현
    public int num;
    public int weight;

    public Node(int num, int weight) {
        this.num = num;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return weight - o.weight;
    }
}

private static void dijkstra(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(start, 0)); // start 지점 등록
    dist[start] = 0; // 자기 자신이므로 가중치 0으로 변경
    boolean[] visited = new boolean[N+1];

    while (!pq.isEmpty()) {
        Node current = pq.poll();
        int currentNum = current.num;

        if (visited[currentNum]) continue;

        visited[currentNum] = true;
        for (Node node : list[currentNum]) {
            if (dist[node.num] > dist[currentNum] + node.weight) { // dist에 기록되어 있는 인접 노드의 가중치 보다 현재 노드의 가중치 + 인접 노드의 가중치가 적다면
                dist[node.num] = dist[currentNum] + node.weight; // 갱신
                pq.add(new Node(node.num, dist[node.num])); // 우선 순위 큐에 갱신 된 노드를 추가
            }
        }
    }
}

위에서 언급한 것 처럼 우선순위 큐를 이용해서 문제를 풀어나갈 수 있다.

• 우선 인접 리스트를 이용하기 위해서는 노드의 번호와 가중치를 저장할 수 있는 Node 클래스를 선언 하고 PriorityQueue에서 비교하기 위해 Comparable을 구현해준다.
• 시작 지점을 먼저 PriorityQueue에 입력해주고 이와 동시에 가중치 배열 내 자기 자신의 가중치를 0으로 갱신한다.
• 이후 PriorityQueue에서 노드를 하나씩 꺼내서 인접 노드를 확인하며 dist에 기록되어 있는 인접 노드의 가중치 보다 현재 노드의 가중치 + 인접 노드의 가중치가 더 적다면 갱신하면 된다.
• PriorityQueue에 갱신 된 노드를 추가하며 위 과정을 반복한다.

구현 - 2중 for문

private static void dijkstraGraph(int start) {
    boolean[] visited = new boolean[N + 1];
    dist[start] = 0;

    for (int i = 1; i <= N; i++) {
        dist[i] = graph[start][i]; // 시작 노드에서 각 노드까지의 초기 거리 설정
    }

    for (int i = 1; i <= N; i++) {
        int currentNum = -1;
        int minDist = INF;

        // 방문하지 않은 노드 중 가장 거리가 짧은 노드 찾기
        for (int j = 1; j <= N; j++) {
            if (!visited[j] && dist[j] < minDist) {
                minDist = dist[j];
                currentNum = j;
            }
        }

        if (currentNum == -1) break; // 더 이상 방문할 노드가 없으면 종료

        visited[currentNum] = true;

        // 현재 노드와 연결된 노드의 거리 업데이트
        for (int j = 1; j <= N; j++) {
            if (!visited[j] && graph[currentNum][j] != INF) {
                dist[j] = Math.min(dist[j], dist[currentNum] + graph[currentNum][j]);
            }
        }
    }
}

다음으로는 2중 for문을 이용하여 문제를 풀어나갈 수 있다.

• 먼저 가중치 배열 내 시작 노드에서 각 노드까지의 가중치를 업데이트 해준다.
• 이후 가장 거리가 짧은 노드를 찾아서 그 노드의 인접노드 부터 탐색을 시작한다.
• 만약 해당 노드를 방문하지 않았고, 가장 거리가 짧은 노드를 통해 해당 노드를 직접적으로 방문할 수 있는 경우에 더 작은 가중치가 있다면 갱신을 진행한다.
• 위 과정을 반복하며 모든 노드에 대해 진행한다.

위와 같이 문제를 풀어나가게 되면 아래와 같이 가중치 배열이 갱신된 것을 볼 수 있다.

[0, 2, 3, 1, 4]

원하는 답은 1 → 5 이므로 정답은 4로 출력된다.

어떤 걸 사용해야할까?

2중 for문을 이용한 선형 탐색의 경우는 최악의 경우 O(N^2)의 시간복잡도를 가지게 된다.

우선순위 큐를 이용하는 방법은 O(N * logN)의 시간복잡도를 가지기에 더 효율적이고 실제로도 이 방법으로 많이 구현된다.

 

또한, 인접행렬과 인접 리스트의 경우는 정점과 간선의 개수에 따라서 선택하는 것이 좋다.

정점 보다 간선의 개수가 많다면 인접행렬, 간선 보다 정점의 개수가 더 많다면 인접리스트를 활용해서 문제를 풀어나가는게 도움이 될 것이다.

 

정리

다익스트라는 한 노드에서 다른 모든 노드까지의 최소 거리를 구하기 위한 알고리즘이다.

일반적으로 인접리스트와 우선순위 큐를 이용한 구현방법이 많이 사용된다.

하지만 정점의 개수와 간선의 개수에 따라 인접행렬과 인접리스트를 선택하고 우선순위 큐를 이용하여 구현하면 대부분의 문제를 해결할 수 있을 것이다.

 

전체 코드

package BaekJoon.Gold.Pr1916;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Pr1916 {

    private static class Node implements Comparable<Node>{
        public int num;
        public int weight;

        public Node(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node o) {
            return weight - o.weight;
        }
    }

    private static int INF = 999999999;
    private static int N, M;
    private static ArrayList<Node>[] list;
    private static int[][] graph;
    private static int[] dist;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        list = new ArrayList[N+1];
        graph = new int[N+1][N+1];
        dist = new int[N+1];

        for (int i = 1; i <= N; i++) {
            dist[i] = INF;
            list[i] = new ArrayList<>();
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (i != j) {
                    graph[i][j] = INF;
                } else {
                    graph[i][j] = 0;
                }
            }
        }

        for (int i = 0; i < M; i ++) {
            st = new StringTokenizer(br.readLine(), " ");

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b, c));
            graph[a][b] = c;
        }

        st = new StringTokenizer(br.readLine(), " ");

        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        dijkstra(start);
        // dijkstraGraph(start);

        System.out.println(dist[end]);
    }

    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        dist[start] = 0;
        boolean[] visited = new boolean[N+1];

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentNum = current.num;

            if (visited[currentNum]) continue;

            visited[currentNum] = true;
            for (Node node : list[currentNum]) {
                if (dist[node.num] > dist[currentNum] + node.weight) { // dist에 기록되어 있는 인접 노드의 가중치 보다 현재 노드의 가중치 + 인접 노드의 가중치가 적다면
                    dist[node.num] = dist[currentNum] + node.weight; // 갱신
                    pq.add(new Node(node.num, dist[node.num])); // 우선 순위 큐에 갱신 된 노드를 추가
                }
            }
        }
    }

    private static void dijkstraGraph(int start) {
        boolean[] visited = new boolean[N + 1];
        dist[start] = 0;

        for (int i = 1; i <= N; i++) {
            dist[i] = graph[start][i]; // 시작 노드에서 각 노드까지의 초기 거리 설정
        }

        for (int i = 1; i <= N; i++) {
            int currentNum = -1;
            int minDist = INF;

            // 방문하지 않은 노드 중 가장 거리가 짧은 노드 찾기
            for (int j = 1; j <= N; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    currentNum = j;
                }
            }

            if (currentNum == -1) break; // 더 이상 방문할 노드가 없으면 종료

            visited[currentNum] = true;

            // 현재 노드와 연결된 노드의 거리 업데이트
            for (int j = 1; j <= N; j++) {
                if (!visited[j] && graph[currentNum][j] != INF) {
                    dist[j] = Math.min(dist[j], dist[currentNum] + graph[currentNum][j]);
                }
            }
        }
    }
}

참고

23. 다익스트라(Dijkstra) 알고리즘