백준 9694 - 무엇을 아느냐가 아니라 누구를 아느냐가 문제다(C++)

문제 링크입니다. https://www.acmicpc.net/problem/9694

9694번: 무엇을 아느냐가 아니라 누구를 아느냐가 문제다

다익스트라와 부모찾기를 이용해 푸는 문제입니다.

한신이와 연결된 사람들을 통해 최소 비용으로 최고 의원을 만날려고 합니다. 이때의 최소 비용을 구하는 문제입니다.

최소 비용을 구하는 것은 다익스트라를 이용해서 쉽게 풀 수 있습니다.

문제는 최고의원을 만나기 까지의 과정을 출력하는 것입니다.

한신이부터 최고의원까지의 과정을 알기 위해서는 자신이 어떤 정점과 연결되어 있는지를 알아야합니다.
자신과 연결된 정점을 알 수 있는 지점은 다익스트라에 존재합니다.
X와 연결된 지점을 Y라고 한다면, Y까지의 비용을 구한 뒤, 이전까지 저장된 Y의 최소 비용을 비교 후, 더 작다면 값을 갱신할 것입니다.
그렇다면, 이때는 X와 Y가 연결되는 과정임으로 해당 과정에서 Y의 부모를 X라고 저장해주면 됩니다.

다익스트라 탐색이 끝난 뒤, 최고의원부터 시작해서 연결된 부모를 찾아가다 보면, 한신이까지 나올 것입니다. 이를 저장해 반대로 출력해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <climits>
#define INF INT_MAX
#define F first
#define S second

using namespace std;

int test_case, N, M;
vector<pair<int, int>> connect[20];
int Distance[20];
int parent[20];
priority_queue<pair<int, int>> q;

void reset_array(){
	for(int i = 0; i < M; i++){
		Distance[i] = INF;
		parent[i] = -1;
	}
}

void Dijstra(){
	Distance[0] = 0;
	q.push({-0, 0});
	parent[0] = 0;
	while(!q.empty()){
		int x = q.top().S;
		int cost = -q.top().F;
		q.pop();
		if(Distance[x] < cost) continue;
		for(int i = 0; i < connect[x].size(); i++){
			int xx = connect[x][i].F;
			int n_cost = connect[x][i].S + cost;
			if(Distance[xx] > n_cost){
				parent[xx] = x; //자신과 연결된 부모 저장
				Distance[xx] = n_cost;
				q.push({-Distance[xx], xx});
			}
		}
	}
}

void solve(int num){
	reset_array();
	Dijstra();
	if(Distance[M-1] != INF){
		vector<int> way;
		way.clear();
		for(int i = M-1; i != 0; i = parent[i]){ // 저장된 부모들을 찾는다.
			way.push_back(i);
		}
		way.push_back(0);
		cout << "Case #" << num << ": ";
		for(int i = way.size()-1; i >= 0; i--){
			cout << way[i] << " ";
		}
		cout << "\n";
	}	
	else{
		cout << "Case #" << num << ": " << "-1" << "\n"; 
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int t = 1; t <= test_case; t++){
		cin >> N >> M;
		for(int i = 0; i < M; i++) connect[i].clear();
		for(int i = 1; i <= N; i++){
			int x, y, cost;
			cin >> x >> y >> cost;
			connect[x].push_back({y, cost});
			connect[y].push_back({x, cost});
		}
		solve(t);
	}
	return 0;
}

질문 및 조언은 댓글을 남겨주세요.