2021년 09월 06일 TIL - 다익스트라 알고리즘 (Java)

짧은 경로

프로그래머스 [가장 먼 노드] 문제를 풀면서 dfs로 해도 되겠지만, 많이 못 써봤던 다익스트라 알고리즘을 사용하면 어떨까 해서 사용해봤는데, 다익스트라 알고리즘에서도 힙 구조를 사용하면 더 효율적으로 사용할 수 있다는 내용이 있어서 한 번 써보았는데 괜찮아져서 TIL에 기록하고 싶다.

---

다익스트라 알고리즘?

다익스트라 알고리즘은 DP

(그 D.P가 아니다)

을 활용한 대표적인 최단 경로 탐색 알고리즘이다.

왜 다이나믹 프로그래밍의 종류이냐? 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징때문이다.

대부분 이차원 배열을 사용하여 선형 탐색을 하는데, 이렇게 작성하면 시간 복잡도가 O(N^2)으로 형성된다.

이를 개선하기 위해 우선 순위 큐의 힙 구조를 활용하여 시간 복잡도 O(N * log N)을 만들 수 있다고 한다.

특히나 선형 탐색을 할 경우 정점의 갯수가 많은데 간선은 적을 때 치명적일 정도로 비효율적으로 작동할 수 있다.

class Pair implements **Comparable<Pair>** { // 리스트에서 정렬을 위한 interface 구현
    public int first;
    public int second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

    @Override
    public int compareTo(Pair o) {
        return this.second <= o.second ? 1 : -1;
    }
}

// ======

class Solution {
    private static final int N = 6;
    private List<Pair>[] edge = new List[N + 1]; // 간선정보
    private int[] d = new int[N + 1]; // 최소 비용

    Solution() {
        // 간선 정보 (예시는 블로그 포스팅 참고)
        edge = new ArrayList<>();
        this.edge[1].add(new Pair(2, 2)); // [Node 1] --- (2: 가중치 ) ---> [Node 2]
        this.edge[1].add(new Pair(3, 5));
        this.edge[1].add(new Pair(4, 1));

        this.edge[2].add(new Pair(1, 2));
        this.edge[2].add(new Pair(3, 3));
        this.edge[2].add(new Pair(4, 2));

        this.edge[3].add(new Pair(1, 5));
        this.edge[3].add(new Pair(2, 3));
        this.edge[3].add(new Pair(4, 3));
        this.edge[3].add(new Pair(5, 1));
        this.edge[3].add(new Pair(6, 5));

        this.edge[4].add(new Pair(1, 1));
        this.edge[4].add(new Pair(2, 2));
        this.edge[4].add(new Pair(3, 3));
        this.edge[4].add(new Pair(5, 1));

        this.edge[5].add(new Pair(3, 1));
        this.edge[5].add(new Pair(4, 1));
        this.edge[5].add(new Pair(6, 2));

        this.edge[6].add(new Pair(3, 5));
        this.edge[6].add(new Pair(5, 2));
    }

    public void    dijkstra(int start) {
        d[start] = 0;
        PriorityQueue<Pair> pq = new PriorityQueue<>(); // 우선순위 큐
        pq.add(new Pair(start, 0));

        while(!pq.isEmpty()) {
            int current = pq.peek().first;
            int distance = -pq.peek().second; // 짧은 것이 먼저 오도록 음수화(-)
            pq.poll();

            if (d[current] < distance) continue; // 최단 거리가 아닌 경우 스킵
            for(int i = 0 ; i < edge[current].size(); i++) {
                int next = edge[current].get(i).first; // 선택된 노드의 인접 노드
                int nextDistnace = distance + edge[current].get(i).second; // 선택된 노드를 인접 노드로 거쳐서 가는 비용

                if (nextDistance < d[next) {  // 기존의 치쇠 비용보다 더 저렴하다면 교체하기
                    d[next] = nextDistance;
                    pq.add(new Pair(next, -nextDistance));
                }
            }
        }
    }

    public void printAll() {
        for(int i = 1 ; i <= N; i++) {
            System.out.println(d[i] + " ");
        }
    }
}

// ======

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.dijkstra(1);
    }
}

알고리즘은 대부분 나동빈님의 블로그에서 참고한다. 자세한 내용은 https://m.blog.naver.com/ndb796/221234424646 에서 찾아보면 될 것 같다.