[알고리즘 TIL] 1753. 최단 경로

문제

https://www.acmicpc.net/status?user_id=rkdduswndi&problem_id=1753&from_mine=1

설명

이 문제는 가중치가 있는 그래프의 최단 경로를 탐색하는 문제이다.

최단 경로를 구하는 알고리즘으로는 bfs와 다익스트라가 있는데, bfs는 가중치가 없는 그래프에 사용되는 알고리즘이고, 다익스트라는 가중치가 있는 그래프에 사용된다.

따라서, 이 문제에서는 우선순위 큐를 적용한 다익스트라 알고리즘을 이용해 최단 경로를 구한다.

의사코드

구현

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.PriorityQueue;

public class Q1753_최단경로_다익스트라 {

    static HashMap<Integer, ArrayList<int[]>> graph = new HashMap<>();
    static int[] result;
    //int[1]을 기준으로 우선순위 정렬
    static PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> Integer.compare(a[1], b[1]));

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputStr = br.readLine().split(" ");
        int V = Integer.parseInt(inputStr[0]); //정점 개수
        int E = Integer.parseInt(inputStr[1]); //간선 개수
        int S = Integer.parseInt(br.readLine()); //시작 정점

        //그래프 정보 저장
        for (int i = 0; i < E; i++) {
            inputStr = br.readLine().split(" ");
            int u = Integer.parseInt(inputStr[0]); //간선 시작점
            int v = Integer.parseInt(inputStr[1]); //간선 도착점
            int w = Integer.parseInt(inputStr[2]); //가중치

            int[] endNodeAndWeight = new int[2];
            endNodeAndWeight[0] = v; endNodeAndWeight[1] = w;

            if(graph.containsKey(u)){
                graph.get(u).add(endNodeAndWeight);
            }else{
                ArrayList<int[]> adjNodes = new ArrayList<>();
                adjNodes.add(endNodeAndWeight);
                graph.put(u, adjNodes);
            }
        }

        //최단 경로 배열  초기화
        result = new int[V + 1];
        Arrays.fill(result, Integer.MAX_VALUE);
        result[S] = 0;

        //우선순위 큐 초기화
        pq.add(new int[]{S, 0});

        //다익스트라 알고리즘
        while (!pq.isEmpty()) {
            int[] pollData = pq.poll();
            int node = pollData[0]; //노드
            int distance = pollData[1]; //거리

            //이미 방문한 노드이면 패스
            if(distance > result[node]) continue;
            //최단 경로 갱신
            result[node] = distance;

            //인접한 노드들 우선순위 큐에 저장
            if(!graph.containsKey(node)) continue;
            for(int[] endNodeAndWeight : graph.get(node)) {
                int adjNode = endNodeAndWeight[0];
                int v = endNodeAndWeight[1];

                int nextDistance = distance + v;
                if(result[adjNode] > nextDistance) {
                    pq.add(new int[]{adjNode, nextDistance});
                }
            }
        }

        for(int i = 1; i < result.length; i++) {
            if(result[i] == Integer.MAX_VALUE) bw.write("INF" + "\n");
            else bw.write(result[i] + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}