[Java] 백준 1753.최단 경로

➡️문제 링크

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

 

 

💡아이디어

다익스트라

정점간의 가중치값이 서로 다른 걸 보고 다익스트라로 접근해야겠다고 생각했다

 

 

✏️문제 풀이

1. 다익스트라 - 성공

시작 정점에서 각 정점까지의 최소 거리값을 저장하는 dist배열을 만들어

pq를 돌려 다음 정점으로 이동할 때 dist에 저장된 값과 비교해 갱신해나간다.

처음에는 꺼낸 정점에서 누적된 가중치와 dist의 값을 비교하지 않았는데,

이미 dist에 저장된 값이 더 작더라면 해당 정점은 더이상 비교할 의미가 생기지 않는 경우가 있다는 걸 깨달았다

그래서 한 번 비교해주고 진행!

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

public class Main {
	static int E, V, K;
	static List<List<int []>> graph = new ArrayList<>();
	static int [] dist;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(br.readLine());	// 정점의 번호
		
		for(int i = 0; i <= V; i++) {
			graph.add(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.get(u).add(new int [] {v, w});
		}
		
		dist = new int[V+1];	// K에서 각 정점마다 최소 거리 
		Arrays.fill(dist, Integer.MAX_VALUE);
		
		
		// 구현
		dijkstra(K);
		
		// 출력
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= V; i++) {
			sb.append(dist[i] != Integer.MAX_VALUE ? dist[i] : "INF" ).append("\n");
		}
		
		System.out.println(sb);
		
	}
	
	static void dijkstra(int start) {
		PriorityQueue<int []> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		pq.add(new int [] {start, 0});	// 출발점
		dist[K] = 0;	// 출발점은 0
		
		while(!pq.isEmpty()) {
			int [] point = pq.poll();
			
			if(point[1] > dist[point[0]]) continue;
			
			List<int []> tmp = graph.get(point[0]);
			for(int i = 0; i < tmp.size(); i++) {
				int [] cur = tmp.get(i);

				if(point[1] + cur[1] < dist[cur[0]]) {
					dist[cur[0]] = point[1]+cur[1];
					pq.add(new int [] {cur[0], dist[cur[0]]});
				}
			}
		}
		
	}

}