[백준/Java] 1753: 최단경로

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

 

 

조건

• TimeLimit = 1s
• 방향 그래프
• 정점(1<=V<=2만), 간선(1<=E<=30만), 가중치(1<=W<=10)
• 시작점이 주어질 때, 1번부터 V번까지 시작점으로부터의 최단거리를 출력하라

 

풀이

• 다익스트라
  • 우선순위 큐를 사용한다면 시간복잡도는 O((V+E)logV)이므로
    -> 대략 O(30만 * log30만) 이므로 충분히 가능
  • 핵심 변수는 대략.. Node = class {idx, w}, graph = List[Node], dist = int[] 정도
  • PriorityQueue의 poll과 offer를 적절히 사용하자

 

코드

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


public class Main {

	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int v;
	static int e;
	static int k;
	static int x;
	static int[] dist;
	static List<Node>[] graph;
	
	
	public static void main(String[] args) throws IOException {

		// input
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		st = new StringTokenizer(br.readLine());
		v = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		
		k = Integer.parseInt(br.readLine());
		
		dist = new int[v+1];
		for (int i=1; i<v+1; i++) dist[i] = Integer.MAX_VALUE;
		
		graph = new ArrayList[v+1];
		for (int i=0; i<v+1; 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 Node(v, w));
		}
		
		// dijkstra
		dijkstra();
		
		// result
		for (int i=1; i<v+1; i++) {
			sb.append(dist[i] != Integer.MAX_VALUE ? dist[i] : "INF").append("\n");
		}
		System.out.print(sb);
		
	}
	
	
	
	static void dijkstra() {
		
		// 초기화
		Queue<Node> q = new PriorityQueue<Node>((o1, o2) -> o1.w - o2.w);
		q.offer(new Node(k, 0));
		dist[k] = 0;
		
		while (!q.isEmpty()) {
			
			// PriorityQueue의 poll과 offer를 사용하므로, 항상 최소 curW가 뽑힌다
			Node curNode = q.poll();
			int curIdx = curNode.idx;
			int curW = curNode.w;
			
			// cur을 지나는게, 현재 등록된 dist보다 비싸면 pass
			// 우선순위큐를 사용하므로, dist[curIdx]가 이미 방문된 상태라면 그 값이 최솟값일것이다
			// 따라서 이 부분이 visited 역할을 해준다 생각하면 됨
			if (dist[curIdx] < curW) continue;
			
			// 탐색
			for (int i=0; i<graph[curIdx].size(); i++) {
				
				Node next = graph[curIdx].get(i);
				int nextIdx = next.idx;
				int cost = curW + next.w;
				
				if (cost < dist[nextIdx]) {
					
					dist[nextIdx] = cost;
					q.offer(new Node(nextIdx, cost));
					
				}
				
			}	
		}	
	}
	
	
	
	static class Node {
		
		int idx;
		int w;
		
		Node(int idx, int w) {
			this.idx = idx;
			this.w = w;
		}
		
	}
	
	
	
}