[백준] 1753번 최단경로 (C++, JAVA)

1753번: 최단경로

graph[정점 A] = (정점 B, A→B 비용)

으로 값을 입력받은 후

 

dist[i] = K→i 비용

을 저장한다.

처음에는 모두 무한대로 저장해 두고

K→K일 때만 0을 저장해준다.

 

우선순위 큐 pq는

비용을 기준으로 오름차순 정렬된다.

제일 처음엔 시작점 K와 K→K 비용 0을 넣어준다.

 

pq의 top에 있는 정점을 mid라 표현할 때,

mid에서 바로 갈 수 있는 정점들 to를 탐색해주며

시작점 K→to 비용보다

시작점 K→mid 비용 + mid→to 비용이 더 작으면

dist[to]를 갱신해주고

pq에도 값을 넣어준다.

 

pq가 빌 때까지 이 과정을 반복하고

dist 값들을 출력시키면 된다.

 

< C++ 코드 >

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include <functional>
using namespace std;
int V, E, K, a, b, c;
int dist[20001];
vector <pair<int, int> > graph[20001];
priority_queue <pair<int, int>, vector<pair<int,int> >, greater<pair<int,int>> > pq;
int main() {
	cin >> V >> E >> K;
	for (int i = 0; i < E; i++) {
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}

	fill(dist, dist + 20001, INT_MAX);
	pq.push(make_pair(0, K));
	dist[K] = 0; // 자기 자신까지의 거리는 0

	while (!pq.empty()) {
		int mid = pq.top().second, mid_dist = pq.top().first;
		pq.pop();
		if (dist[mid] > mid_dist) continue; // pq에 저장돼 있는 거리보다 짧은 값이 저장돼 있으면 넘어간다
		
		for (int i = 0; i < graph[mid].size(); i++) {
			if (dist[graph[mid][i].first] > dist[mid] + graph[mid][i].second) { // K에서 현재 정점으로 갈 때 거리 > K에서 mid까지 거리 + mid에서 현재 정점까지의 거리
				dist[graph[mid][i].first] = dist[mid] + graph[mid][i].second;
				pq.push(make_pair(dist[graph[mid][i].first], graph[mid][i].first));
			}
		}
	}

	for (int i = 1; i <= V; i++) {
		if (dist[i] == INT_MAX) cout << "INF\n";
		else cout << dist[i] << "\n";
	}
	return 0;
}

 

< JAVA 코드 >

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BOJ_1753_최단경로 {
	static int V, E, K, current, currentWeight, goal, goalWeight, weight;
	static int distance[];
	static PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)->o1[1]-o2[1]);
	static ArrayList<int[]> graph[];
	
	static int stoi(String st) { return Integer.parseInt(st); }
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		V = stoi(st.nextToken()); E = stoi(st.nextToken()); K = stoi(br.readLine());
		distance = new int[V + 1]; graph = new ArrayList[V + 1];
		for(int i = 1; i <= V; i++) graph[i] = new ArrayList<>(); // ArrayList 배열로 선언해서 초기화 이렇게 해줌
		for(int i = 0; i < E; i++) {
			st = new StringTokenizer(br.readLine());
			graph[stoi(st.nextToken())].add(new int[] {stoi(st.nextToken()), stoi(st.nextToken())});
		} // 입력
		
		Arrays.fill(distance, Integer.MAX_VALUE); // 모든 정점의 값 무한대로 지정
		distance[K] = 0; // 시작 정점의 값은 0
		pq.offer(new int[] {K, 0}); // 최솟값 정점 찾기 위해 우선순위 큐 사용
		
		while(!pq.isEmpty()) {
			current = pq.peek()[0]; currentWeight = pq.poll()[1]; // 경유지
			if(currentWeight > distance[current]) continue; // 아까 큐에 넣은 값보다 현재 갱신돼있는 값이 더 작으면 계산할 필요 없으므로 넘김
			for(int i = 0; i < graph[current].size(); i++) {
				goal = graph[current].get(i)[0];
				goalWeight = graph[current].get(i)[1];  
				if(distance[goal] > distance[current] + goalWeight) {
					distance[goal] = distance[current] + goalWeight; // (K->goal) > (K->current + current->goal) 이면 갱신
					pq.offer(new int[] {goal, distance[goal]}); // 새 값 넣음
				}
			}
		}
		
		for(int i = 1; i <= V; i++) System.out.println(distance[i] == Integer.MAX_VALUE ? "INF":distance[i]);
	}
}