[BAEKJOON] 백준 다익스트라 1753 :: 최단 경로

💬  문제 설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.

단, 모든 간선의 가중치는 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를 출력하면 된다.
  

 

예제 입력 1)

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

 

예제 출력 1)

0
2
3
7
INF

 

​

💻  Main.java

• 그래프를 2중 연결 리스트로 표현해준다
• 갱신 된 노드를 저장하기 위한 우선순위 큐를 사용
  • 이때 우선 순위 큐를 항상 최단 경로 순으로 정렬이 보장된다
• 최단 경로는 저장하기 위해 int 배열 result를 생성해줬다
•  

/* 백준 다익스트라 - 1753 :: 최단경로 */
import java.util.*;
import java.io.*;

class Node implements Comparable<Node>{
	int index;
	int distacne;

	Node(int index, int distacne) {
		this.index = index;
		this.distacne = distacne;
	}
	
	@Override
	public int compareTo(Node o) {
	return Integer.compare(this.distacne, o.distacne);
	}
}

public class Main {
	static final int INF = 9999999;
	static List<List<Node>> graph = new ArrayList<>();
	static int[] result;	
		
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner (System.in);
		int v = sc.nextInt();
		int e = sc.nextInt();
		int k = sc.nextInt();
		
		for(int i = 0; i <= v; i++) {
			graph.add(new ArrayList<>());
		}
		
		result = new int[v + 1];
		Arrays.fill(result, INF);
		
		// 문제에서 주어진 입력 값에 따라 그래프 초기화
		for (int i = 0; i < e; i++) {
			graph.get(sc.nextInt()).add(new Node(sc.nextInt(), sc.nextInt()));
		}
		
		// 다익스트라 알고리즘 수행
		dijkstra(k);
		
		// 문제에서 제시한 조건에 맞게 출력
		for (int i = 1; i < result.length; i++) {
			if(result[i] == INF) {
				System.out.println("INF");	
			}else {
				System.out.println(result[i]);
			}
		}
        sc.close();
	}
	
	static void dijkstra(int start) {
		// 최단거리가 갱신 된 노드들을 담을 우선순위 큐 생성
		PriorityQueue<Node> pq =  new PriorityQueue<>();
		result[start] = 0;
		
		pq.offer(new Node(start, result[start]));
		
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int nodeIndex = node.index;
			int distance = node.distacne;
			
			// 중복 방문 검사
			if(distance > result[nodeIndex]) {
				continue;
			}
			
			for (Node linkedNode : graph.get(nodeIndex)) {
				// 새로 찾은 값이 최단 거리면, 최단 거리 갱신해주기
				if(distance + linkedNode.distacne < result[linkedNode.index]) {
					result[linkedNode.index] = distance + linkedNode.distacne;
					pq.offer(new Node(linkedNode.index, result[linkedNode.index]));
				}
			}
		}
	}
}