[Gold IV] 최단경로 - 1753

[Gold IV] 최단경로 - 1753

문제 링크

성능 요약

메모리: 108700 KB, 시간: 656 ms

분류

데이크스트라, 그래프 이론, 최단 경로

제출 일자

2024년 11월 18일 14:21:12

문제 설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

---

다익스트라 알고리즘을 통해 시작점으로부터 모든 정점까지의 거리를 구해 문제를 해결해보자

컴퓨터 과학에서 데이크스트라 알고리즘(영어: Dijkstra algorithm) 또는 다익스트라 알고리즘은 도로 교통망 같은 에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 컴퓨터 과학자 에츠허 이크스트라가 1956년에 고안했으며 삼 년 뒤에 발표했다.

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

1. Node 클래스를 만들어서 노드 번호와 가중치를 관리하자
   • Node 클래스의 사용 목적은 특정 노드(인접 리스트에서 인덱스로 관리)가 해당 노드로 도착하기 위한 정보를 제공하는 것
   • 목적지(dest)와 비용(cost)을 가진 Node 객체로 그래프의 간선 정보를 표현
2. 인접리스트를 생성하고 각 노드가 갈 수 있는 노드과 그에 따른 비용을 관리하자
   • adjList[출발점]에 (도착점, 비용) 정보를 담은 Node 객체들을 저장
3. 우선순위 큐로 가중치가 낮은 노드를 먼저 불러와 각 지점까지 최소 비용으로 이동할 수 있도록 하자
   • 비용(cost) 기준으로 오름차순 정렬되도록 Comparator 설정

 

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

class Main {
    private static class Node{
        int dest, cost;
        public Node(int dest, int cost){
            this.dest = dest;
            this.cost = cost;
        }

    }

    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()); // 간선의 개수
        Node startNode = new Node(Integer.parseInt(br.readLine()), 0);

        boolean[] visited = new boolean[V+1];
        int[] dist = new int[V+1];

        // 인접 리스트 생성 및 초기화
        List<Node>[] adjList = new List[V+1];

        for(int i=1; i<=V; i++){
            adjList[i] = new ArrayList<>();
        }

        for(int i=0; i<E; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            adjList[from].add(new Node(to, cost));
        }

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[startNode.dest] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        pq.add(startNode);

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            if(visited[cur.dest])
                continue;

            visited[cur.dest] = true;

            for(Node next :adjList[cur.dest]){
                if(dist[next.dest] > cur.cost + next.cost){
                    dist[next.dest] = cur.cost + next.cost;
                    pq.add(new Node(next.dest, dist[next.dest]));
                }
            }
        }

        StringBuilder sb = new StringBuilder();

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

        System.out.println(sb);

        br.close();
    }
}