[백준/Java] 1753번 : 최단경로 / 다익스트라(dijkstra)

가장 기본적인 다익스트라 알고리즘 문제이다.

 

다익스트라 알고리즘을 처음 접한다면 아래 글을 한번 읽어보는 것을 추천한다.

2023.06.26 - [자료구조_알고리즘/Algorithm] - [Algorithm] 다익스트라(dijkstra) 알고리즘 (최단거리, 가중치 그래프)

---

우선 Edge 클래스를 하나 만들어서 해당 edge가 가리키는 노드, 가중치를 저장한다.

출발 노드는 ArrayList의 index로 관리할 것이기 때문에 필요 없다.

 

그래프 정보를 저장할 ArrayList<Edge>[ ] 배열과 최단거리 배열 int[ ] distance를 만들고, 초기화 한다.

 

각 Edge의 가중치가 작은 것 부터 poll() 할수 있는 우선순위 큐를 만들고 시작점을 먼저 넣는다.

 

이후 우선순위 큐에서 Edge를 하나씩 꺼내며, Edge가 가리키는 최단거리 배열의 값과 비교하며 업데이트 해 나간다.

 

처음에 출발점 Edge에서 출발하기 때문에 distance[start] = 0으로 초기화 하는것을 잊지 말자!

---

Code

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 Main{

    static class Edge {
        int to; //가리키는 노드
        int weight; //가중치

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static int V, E, start; //노드 개수, 간선 개수, 시작점
    static ArrayList<Edge>[] graph;
    static int[] distance;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());
        distance = new int[V+1];
        graph = new ArrayList[V+1];
        
	// 최단거리 배열 초기화
        for (int i = 0; i <= V; i++) {
            distance[i] = Integer.MAX_VALUE;
        }
        distance[start] = 0;
        
	// 그래프 초기화
        for (int i = 0; i <= V; i++) {
            graph[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());
            graph[u].add(new Edge(v,w));
        }
        //=== 초기화 끝 ===

        //=== 다익스트라 시작 ===
        PriorityQueue<Edge> pq = new PriorityQueue<>((x, y)-> x.weight - y.weight);
        pq.add(new Edge(start, 0));
        
        while(!pq.isEmpty()){
            Edge cur = pq.poll();

            //최단거리 배열의 값이 현재 에지의 가중치보다 작으면 continue
            if(distance[cur.to] < cur.weight){
                continue;
            }
            for (int i = 0; i < graph[cur.to].size(); i++) {
                Edge tmp = graph[cur.to].get(i);
                int next = tmp.to;
                int weight = tmp.weight;

                if(distance[next] > distance[cur.to] + weight) {
                    distance[next] = distance[cur.to] + weight;
                    pq.offer(new Edge(next, distance[next]));
                }
            }
        }
        
        // 출력
        for (int i = 1; i <= V ; i++) {
            if(distance[i] == Integer.MAX_VALUE){
                System.out.println("INF");
            }else{
                System.out.println(distance[i]);
            }
        }
    }
}