백준 1854 c++ "K번째 최단경로 찾기" -PlusUltraCode-

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

 

[필자 사고]

 

이 문제를 리뷰해보자면 다익스트라 알고리즘을 이용하여 최단거리를 구하는 문제의 변형이라고 생각한다.

그동안 최단거리의 경로만 구해왔었지만 이 문제만의 특별한 점은 K번째 최단거리라는 점이다.

그러한 이유로 기존 int Distance[] 를 이용했던 필자는 우선순위 큐 List 를 사용하여 문제를 해결했다.

arr는 정방향 그래프를 저장하는 2차원 벡터이다. arr[s]는 s 노드에서 갈 수 있는 다음 노드와 그 간선의 가중치(시간)를 저장한다.

pqList는 각 노드에서 K번째 최단 경로를 저장하는 우선순위 큐(최대 힙)를 저장하는 벡터다.

pqList[nextNum]는 nextNum 노드까지의 K번째 최단 경로들을 저장한다.
visited는 BFS를 수행할 때 노드 방문 여부를 체크하는 벡터이다.
N, M, K는 각각 노드의 개수, 간선의 개수, 그리고 찾고자 하는 경로의 수(K)를 의미한다.

입력 처리 (Input 함수)
Input() 함수는 노드 개수(N), 간선 개수(M), 그리고 찾고자 하는 경로의 수(K)를 입력받는다.
그 후 각 간선 정보를 입력받아 arr에 저장한다. 각 간선은 출발지(s), 도착지(e), 가중치(w)로 이루어진다.

BFS 함수
BFS() 함수는 1번 노드에서 시작하여 우선순위 큐를 이용해 BFS를 수행한다. 우선순위 큐는 경로의 가중치가 작은 순서대로 정렬된다.
pqList는 각 노드로 도달하는 경로의 가중치를 저장하며, 그 중 가장 큰 경로부터 저장된다.
만약 경로의 개수가 K개 이상이면, 그 중 가장 작은 값을 유지하기 위해 큐에서 제거하는 방식으로 K번째 최단 경로를 유지한다.
만약 경로의 가중치가 큐에 있는 최대값보다 작을 경우, 그리고 큐의 크기가 K번째인 경우 큐에서 해당 값을 제거하고 새로운 값을 추가한다.

게임 시작 (GameStart 함수)
GameStart() 함수는 BFS를 통해 모든 경로 계산이 끝난 후, 각 노드에서 K번째 최단 경로를 출력한다.
만약 K번째 경로가 존재하지 않으면 -1을 출력하고, 존재하면 그 값을 출력한다.

 

 

[소스 코드]

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

using namespace std;
typedef pair<int, int> Node;

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

using namespace std;
typedef pair<int, int> Node;
const int MAX_INT = 99999999;
int N, M, K;
vector<vector<Node>> arr;
vector<priority_queue<int, vector<int>>> pqList;

void Input() {
	cin >> N >> M >> K;
	arr.resize(N + 1);
	pqList.resize(N + 1);


	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		arr[s].push_back({ w,e });
	}

}

vector<bool> visited;

void BFS() {
	priority_queue<Node, vector<Node>, greater<Node>> pq;
	visited.resize(N + 1, false);
	pq.push({ 0,1 });

	pqList[1].push(0);

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

		for (Node nextNode : arr[nowNum]) {
			int nextNum = nextNode.second;
			int nextWeight = nextNode.first;

			if (pqList[nextNum].size() == 0) {
				pqList[nextNum].push(nowWeight + nextWeight);
				pq.push({ nowWeight + nextWeight,nextNum });
				continue;
			}

			if (pqList[nextNum].top() > nowWeight + nextWeight) {
				//넣어야되는데 꽉찼으면 하나 빼야돼
				
				if (pqList[nextNum].size() >= K) {
					pqList[nextNum].pop();
				}
				pqList[nextNum].push(nowWeight + nextWeight);
				pq.push({ nowWeight + nextWeight,nextNum });

				continue;
			}
			else {
				if (pqList[nextNum].size() < K) {

					pqList[nextNum].push(nowWeight + nextWeight);
					pq.push({ nowWeight + nextWeight,nextNum });
				}
			}
			
		}
	}
}



void GameStart() {
	BFS();
	for (int i = 1; i <= N; i++) {
		if (pqList[i].size() < K) {
			cout << -1 << '\n';
		}
		else {
			cout << pqList[i].top() << '\n';
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	Input();
	GameStart();
}