[백준] 최단 경로 : 1753 : Java - 다익스트라(Dijkstra)

1. 문제

1753번: 최단경로

- 주어진 한 정점 부터 각 모든 정점 최소 경로 구하기

 

---

2. 해결 포인트

이 문제는 주어진 노드의 제한이 크기 때문에 정점마다 탐색을 진행할 수 없다. 최소 경로 문제에 쓰이는 알고리즘이 필요하다.

한 노드에서 각 모든 노드까지 가는 최단 경로를 구할 수 있는 다익스트라 알고리즘을 쓴다.

 

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

한 노드에서 각 모든 노드까지 가는 최단 경로를 구하는 알고리즘. 음의 간선을 포함할 수 없다.

시간 복잡도 : O((V+E)log V) - 우선 순위 큐 이용할 때, 일반적 O(V^2)

 

 

다익스트라 알고리즘 매커니즘

• 기본적으로 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이다.
• 기본적으로 아래 두 단계를 반복하여 임의의 노드에서 각 모든 노드까지 최단거리를 구한다. 

        (1) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다(그리디 알고리즘).

        (2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다(다이나믹 알고리즘).  

   

코드로 확인해 보자. 가장 가중치가 작은 노드를 뽑기 위해 우선 순위 큐 자료구조를 이용한다. 우선 순위 큐에서 가장 첫번째 노드를 확인할 때 방문하지 않은 노드라면 해당 노드를 선택하고, 해당 노드로부터 이어진 노드들의 비용을 갱신해준다. 이때 갱신은 현재 거리보다 작아질 수 있을 때만 갱신해준다. 누적된 값으로 갱신한다는 것에 주의하자. 

public static void dijkstra(int start){
        // 가장 가중치가 작은 값을 뽑기 위해 우선순위 큐 사용
       PriorityQueue<Node> que = new PriorityQueue<>();
       que.add(new Node(start, 0));

       while(!que.isEmpty()){
           // (1) 방문하지 않은 노드 중 가장 적은 노드를 선택한다.
           Node curNode = que.poll();
           // 방문한 노드라면 넘어간다
           if(isVisited[curNode.value])
               continue;
           // 방문하지 않은 노드라면 방문한다.
           isVisited[curNode.value] = true;

           // (2) 해당 노드로부터 갈 수 있는 비용을 갱신한다. (작을 때만 갱신)
           for(Node node : trees.get(curNode.value)){
               if(ans[node.value] > ans[curNode.value] + node.weight){
                   ans[node.value] = ans[curNode.value] + node.weight;
                   que.add(new Node(node.value, ans[node.value]));
               }
           }
       }
    }

 

정렬 기준 결정 : CompareTo 오버라이딩

우선순위의 큐에서 정렬 순서를 결정할 때 내부적으로 `compareTo` 함수를 호출한다. 그러므로 사용자 정의 객체를 사용한다면 `Comparable<Object>`을 implements하여 `compareTo`함수를 오버라이딩 해야한다.

class Node implements Comparable<Node>{
    int value;
    int weight;

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


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

 

3. 전체 코드

다익스트라 알고리즘을 구현하면 풀 수 있는 문제이다 (나는 몰랐다!).

import javax.swing.text.html.ListView;
import java.io.*;
import java.util.*;

public class Main {
    public static int [] ans;
    public static boolean [] isVisited;
    public static ArrayList<Node>[] trees;
    public static void main(String [] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        int start = Integer.parseInt(br.readLine());
        trees = new ArrayList[V+1];
        ans = new int[V+1];
        isVisited = new boolean[V+1];
        for(int i=1; i<=V; i++){
            trees[i] = new ArrayList<>();
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            Node node = new Node(v, w);
            // 단방향 간선 생성
            trees[u].add(node);
        }

        // 최소 거리를 담을 배열 초기화
        for(int i=1; i<=V; i++){
            ans[i] = Integer.MAX_VALUE;
        }

        ans[start] = 0;
        dijkstra(start);

        // 출력
        for(int i=1; i<=V; i++){
            if(i == start)
                bw.write(0+"\n");
            else if(ans[i] == Integer.MAX_VALUE)
                bw.write("INF\n");
            else
                bw.write(ans[i]+"\n");
        }

        bw.flush();
    }

    public static void dijkstra(int start){
        // 가장 가중치가 작은 값을 뽑기 위해 우선순위 큐 사용
       PriorityQueue<Node> que = new PriorityQueue<>();
       que.add(new Node(start, 0));

       while(!que.isEmpty()){
           // 방문하지 않은 노드 중 가장 적은 노드를 선택한다.
           Node curNode = que.poll();
           // 방문한 노드라면 넘어간다
           if(isVisited[curNode.value])
               continue;
           // 방문하지 않은 노드라면 방문한다.
           isVisited[curNode.value] = true;

           // (2) 해당 노드로부터 갈 수 있는 비용을 갱신한다. (작을 때만 갱신)
           for(Node node : trees[curNode.value]){
               if(ans[node.value] > ans[curNode.value] + node.weight){
                   ans[node.value] = ans[curNode.value] + node.weight;
                   que.add(new Node(node.value, ans[node.value]));
               }
           }
       }
    }

}

class Node implements Comparable<Node>{
    int value;
    int weight;

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


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