취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9694번 문제인 무엇을 아느냐가 아니라 누구를 아느냐가 문제다이다.
문제는 아래 링크를 확인하자.

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

문제의 상황을 각 정치인을 노드로, 서로 친한 관계를 그 관계의 친밀도를 가중치로 갖는 에지로 갖는 그래프로 모델링하자. 이 때, 주어진 문제는 0번 노드에서 M-1번 노드까지의 최단경로 중 하나를 구해내는 문제로 생각할 수 있다.

다익스트라(dijkstra) 알고리즘 등을 이용해 최단경로를 구해 문제를 해결하자. 글쓴이는 실제 경로를 역추적하기 위해 거리를 갱신할 때마다 어떤 노드에서 해당 노드로 이동했는지를 기록해두는 backtrack 배열을 아래와 같이 관리해 문제를 해결하였다.

memset을 쓰면스 cstring 헤더를 include하지 않아 컴파일에러를 한번 받았다...

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int T;
int N, M;
vector<pair<int, int>> G[20];
int dist[20];
int backtrack[20];

void dijkstra() {
	dist[0] = 1;
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> pq;
	pq.push(make_pair(1, 0));

	while (!pq.empty()) {
		int cur = pq.top().second, d = pq.top().first; pq.pop();
		if (dist[cur] < d) continue;
		
		for (auto& p : G[cur]) {
			int nxt = p.first, w = p.second;
			if (dist[nxt] == 0 || d + w < dist[nxt]) {
				dist[nxt] = d + w;
				backtrack[nxt] = cur;
				pq.push(make_pair(d + w, nxt));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> T;
	for (int t = 1; t <= T; t++) {
		cin >> N >> M;
		memset(dist, 0, sizeof(dist));
		for (int i = 0; i < M; i++) G[i].clear();
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < M; j++) {
				backtrack[i] = -1;
			}
		}

		while (N--) {
			int x, y, w; cin >> x >> y >> w;
			G[x].emplace_back(make_pair(y, w));
			G[y].emplace_back(make_pair(x, w));
		}

		dijkstra();

		cout << "Case #" << t << ": ";

		if (backtrack[M - 1] < 0) cout << -1 << '\n';
		else {
			vector<int> ans;
			int cur = M - 1;
			while (backtrack[cur] > -1) {
				ans.emplace_back(cur);
				cur = backtrack[cur];
			}

			cout << 0 << ' ';
			while (!ans.empty()) {
				cout << ans.back() << ' ';
				ans.pop_back();
			}

			cout << '\n';
		}
	}
}