백준 1753 c++ "최단경로" -PlusUltraCode-

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

 

[필자 사고]

먼저, 입력을 처리하는 함수가 있다.

이 함수는 노드의 수, 간선의 수, 시작 노드 번호를 입력받고,

정방향 그래프를 저장할 2차원 벡터 arr, 방문 여부를 기록할 벡터

visited, 그리고 각 노드까지의 최단 거리를 저장할 벡터 Distance를 초기화한다.

초기화 과정에서 Distance 벡터는 매우 큰 값으로 채워지는데,

이는 아직 어떤 노드까지의 최단 거리가 계산되지 않았음을 의미한다.

 

다음으로, BFS(우선순위 큐를 활용한 다익스트라 알고리즘)를 수행하는 함수가 있다.

이 함수는 우선순위 큐를 사용해 시작 노드에서 출발하여, 다른 모든 노드까지의 최단 거리를 계산한다.

알고리즘은 각 노드에 대해 현재까지 계산된 최단 거리가 더 짧은 경로가 발견되면 이를 갱신하고,

그 노드를 우선순위 큐에 다시 추가하는 방식으로 작동한다.
다익스트라 알고리즘의 핵심은 내가 방문한 시점에서 그 노드는 최단거리로 왔다는 점이다. 
이러한 특성을 활용하여 vistited[] 를 아래 코드와 같이 구현해야 된다.

 

 

마지막으로, GameStart 함수는 계산된 최단 거리를 출력한다. 만약 어떤 노드에 도달할 수 없으면 "INF"를 출력하고, 도달할 수 있는 경우에는 그 노드까지의 최단 거리를 출력한다.

 

[소스 코드]

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<long, int> Node;
int V, E, K;
vector<vector<Node>> arr;
vector<bool> visited;
vector<long> Distance;

void Input() {
	cin >> V >> E >> K;
	arr.resize(V+1);
	Distance.resize(V + 1,999999999);
	visited.resize(V + 1, false);
	for (int i = 0; i < E; i++) {
		int s, e;
		long w;
		cin >> s >> e >> w;

		arr[s].push_back({ w,e });

	}
}


void BFS() {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	pq.push({ 0,K });
	visited[K] = true;
	Distance[K] = 0;

	while (!pq.empty()) {
		int nowNum = pq.top().second;
		long nowWeight = pq.top().first;
		pq.pop();

		visited[nowNum] = true;


		for (Node nextNode : arr[nowNum]) {
			int nextNum = nextNode.second;
			long nextWeight = nextNode.first;
			if (visited[nextNum])continue;
			if (Distance[nextNum] > Distance[nowNum] + nextWeight) {
				Distance[nextNum] = Distance[nowNum] + nextWeight;
				pq.push({ Distance[nextNum],nextNum });
			}
		}
	}
}

void GameStart() {
	BFS();
	for (int i = 1; i <=V; i++) {
		if (Distance[i] == 999999999) {
			cout << "INF" << '\n';
		}
		else {
			cout << Distance[i] << '\n';
		}
	}

}


int main(void) {
	Input();
	GameStart();
}