[백준] 1753번 최단경로(java)

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

1753번: 최단경로

다익스트라 문제이다.

 

핵심

이 문제는 가중치가 있는 다익스트라 문제이다.

가중치가 있기 때문에 클래스를 구현하는 것이 편리하다.

 

 

정답 코드

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

public class Main{
    static List<Node>[] nodes;
    static boolean[] check;
    static int[] distance;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] vAndE = br.readLine().split(" ");
        int v = Integer.parseInt(vAndE[0]);
        int e = Integer.parseInt(vAndE[1]);
        nodes = new ArrayList[v+1];
        check = new boolean[v+1];
        distance = new int[v+1];

        int start = Integer.parseInt(br.readLine());
        for (int i = 0; i <= v; i++){
            nodes[i] = new ArrayList<>();
            distance[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < e; i++){
            String[] info = br.readLine().split(" ");
            int from = Integer.parseInt(info[0]);
            int to = Integer.parseInt(info[1]);
            int value = Integer.parseInt(info[2]);
            nodes[from].add(new Node(to, value));
        }

        StringBuilder sb = new StringBuilder();
        dij(start);
        for (int i = 1; i <=v; i++){
            if (distance[i] == Integer.MAX_VALUE) {
                sb.append("INF").append("\n");
            } else {
                sb.append(distance[i]).append("\n");
            }
        }
        System.out.println(sb);
    }

    public static void dij(int start){
        PriorityQueue<Node> q = new PriorityQueue<>();
        distance[start] = 0;
        q.offer(new Node(start,0));

        while (!q.isEmpty()){
            Node cur = q.poll();
            check[cur.end] = true;
            for(Node node : nodes[cur.end]){
                if (!check[node.end]){
                    if (distance[cur.end] + node.cost < distance[node.end]){
                        distance[node.end] = distance[cur.end] + node.cost;
                        q.offer(new Node(node.end, distance[node.end]));
                    }
                }
            }
        }
    }
}

class Node implements Comparable<Node>{
    public int end;
    public int cost;

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

    public Node(int end, int cost) {
        this.end = end;
        this.cost = cost;
    }
}

해설

우선순위 큐를 사용하기 위해 Node의 compareTo를 재정의하였다.

시작점을 0으로 저장하고 1에서 갈 수 있는 노드들의 값을 변경시킨다.

distance배열에서 아직 방문하지 않고, 최솟값을 기준으로 갈 수 있는 노드들의 값들을 변경시킨다.

이후 노드 1번부터 v까지 방문할 수 있는 경우의 최단경로를 출력한다.

만약 갱신이 안된 상태는 방문을 할 수 없다는 것을 의미한다.

 

배운 점

이전에 다익스트라를 다른 방식으로 풀어왔다.

우선순위 큐를 사용하니 조금 더 직관적이고, 이해하기 쉽다고 생각한다.

다익스트라가 쉬운 알고리즘이 아니기 때문에 연습이 필요할 것 같다.