[Java] 최단경로 - 다익스트라 (Lv. Gold4)

최단경로 - 다익스트라 (Lv. Gold4)

---

1. 문제

2. 풀이

---

1. 문제

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

 

2. 풀이

import java.util.*;
import java.io.*;

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

public class Main {
    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());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());
        
        boolean[] visit = new boolean[V + 1];
        int[] result = new int[V + 1];
        List<Node>[] list = new List[V + 1];

        for (int i = 0; i <= V; i++) {
            list[i] = new ArrayList<>();
            result[i] = Integer.MAX_VALUE;
        }

        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());

            list[u].add(new Node(v, w));
        }
        
        PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);
        result[K] = 0;
        queue.add(new Node(K, 0));
        
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            if (visit[now.end]) continue;
            visit[now.end] = true;
            
            for (Node next : list[now.end]) {
                if (!visit[next.end] && result[now.end] + next.weight < result[next.end]) {
                    result[next.end] = result[now.end] + next.weight;
                    queue.add(new Node(next.end, result[next.end]));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (result[i] == Integer.MAX_VALUE) sb.append("INF\n");
            else sb.append(result[i]).append("\n");
        }
        System.out.print(sb);
    }
}

 

- PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);

우선순위 큐에서 비교할 기준을 정의합니다.

o1과 o2는 Node 객체 두 개이고, 우선순위 큐는 o1과 o2를 비교하여 어떤 객체가 더 우선순위가 높은지 결정합니다.

o1.weight가 o2.weight 보다 작으면 우선순위가 o1이 더 높습니다.

 

- queue.add(new Node(K, 0));

우선순위 큐에 Node(K, 0)을 추가합니다.

시작점의 가중치는 0으로 설정되고 그 노드부터 탐색을 하게 됩니다.

 

- if (visit[now.end]) continue;

큐가 비지 않으면 반복합니다. queue.poll()을 통해 우선순위 큐에서 가중치가 가장 작은 노드를 꺼냅니다.

visit[now.end]가 true라면 이미 방문한 노드이므로 건너뛰고 새로운 노드를 처리합니다.

 

for (Node next : list[now.end]) {
    if (!visit[next.end] && result[now.end] + next.weight < result[next.end]) {
        result[next.end] = result[now.end] + next.weight;
        queue.add(new Node(next.end, result[next.end]));
    }
}

 

list[now.end]는 현재 now.end 노드와 인접한 노드들을 담고 있는 리스트입니다.

Node next는 now.end에서 출발하는 각각의 인접 노드와 그 노드까지 가는 간선의 가중치를 나타냅니다.

 

visit[next.end]가 false일 경우에 아직 방문을 하지 않았다는 뜻이므로 !visit[next.end]를 해서 true로 반환하여 방문을 할 수 있습니다.

현재 now.end에서 next.end까지 가는 경로의 총 비용과 next.end까지 이미 계산된 경로보다 짧으면 경로를 갱신합니다.

 

갱신된 result[next.add] 값을 바탕으로 next.end 노드를 우선순위 큐에 추가합니다.

---

문제가 있으면 댓글 남겨주세요 !

피드백은 언제나 환영입니다 <3