취미로 코딩하기

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

이번에 볼 문제는 백준 28073번 문제인 PSAT 특별과정이다.
문제는 아래 링크를 확인하자.

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

가장 적은 '문제'를 푸는 경로는 BFS를 이용해서 간단하게 구해낼 수 있다. 이 중 사전순으로 가장 빠른 경로를 찾으려면 어떻게 해야할까?

모든 '문제'가 갖는 가중치가 서로 다르다면 bfs 과정에서 각 노드에서 다음 노드를 큐(queue)에 담을 때 가중치가 증가하는 순서대로 담는 것으로 문제를 해결할 수 있을 것이다. 이와 같이 탐색하면 탐색 과정에서 나오는 같은 길이의 경로들끼리 비교했을 때 먼저 나오는 경로가 사전순으로 앞서게 되기 때문이다.

그러나 이 문제에서는 각 '문제'가 갖는 가중치에 중복이 있으므로 이에 유의해야 한다. 문자 S를 출력하게 되는 문제와 연결되어 있는 가중치가 같은 서로 다른 두 노드 A1과 A2, 그리고 가중치가 B>C인 두 노드 B와 C가 있는 경우를 생각해보자. 탐색과정에서 A1을 SA2보다 먼저 방문하고 A1에서 다음으로 탐색할 수 있는 후보가 B, A2에서 다음으로 탐색할 수 있는 후보가 C뿐이라면 위와 같은 방식으로 탐색을 하면 SA1B가 SA2C보다 먼저 등장하게 된다. 그러나 SA2C가 SA1B보다 사전순으로 앞서므로 이 방법을 수정하지 않으면 문제의 답을 올바르게 낼 수 없다.

당장은 같은 가중치를 가져 사전순에 영향을 주지 않지만 이후의 탐색 과정에서 가중치가 역전되어 사전순에 영향을 줄 수 있는 경우가 문제이므로, 이를 해결하기 위해 BFS 탐색 중 현재 노드에서 방문할 수 있는 중복된 가중치를 갖는 노드가 존재하는 경우를 만날 때마다 해당 노드들을 합쳐 새로운 노드를 만들어주자. 이와 같이 구현하면 위와 같은 문제를 피해 올바른 답을 구해낼 수 있다.

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

int N, M; char S, E;
vector<int> G[1000002];
int prv[1000002];
string L;

bool comp(int& x, int& y) {
	return L[x] < L[y];
}

queue<int> que;
void bfs() {
	que.push(N + 1); prv[N + 1] = -1;
	for (int i = 1; i <= N; i++) {
		if (L[i] == S) G[N + 1].emplace_back(i);
	}

	for (int i = 0; i <= N; i++) sort(G[i].begin(), G[i].end(), comp);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		if (L[cur] == E) {
			string ans = "";
			while (prv[cur] > 0) {
				ans += L[cur];
				cur = prv[cur];
			}

			while (!ans.empty()) {
				cout << ans.back();
				ans.pop_back();
			}
			return;
		}
		int old = 0; char oldchar = ' '; set<int> st;
		for (auto& nxt : G[cur]) {
			if (prv[nxt]) continue;
			prv[nxt] = cur;
			if (L[nxt] != oldchar) {
				if (old) {
					set<int> stst;
					for (auto& x : st) {
						for (auto& xx : G[x]) {
							stst.insert(xx);
						}
					}
					G[old].clear();
					for (auto& xxx : stst) G[old].emplace_back(xxx);
					sort(G[old].begin(), G[old].end(), comp);
					st.clear();
					que.push(old);
				}
				old = nxt, oldchar = L[nxt];
			}

			st.insert(nxt);
		}

		if (old) {
			set<int> stst;
			for (auto& x : st) {
				for (auto& xx : G[x]) {
					stst.insert(xx);
				}
			}
			G[old].clear();
			for (auto& xxx : stst) G[old].emplace_back(xxx);
			sort(G[old].begin(), G[old].end(), comp);
			st.clear();
			que.push(old);
		}
	}

	cout << "Aaak!";
}

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

	cin >> N >> M >> S >> E >> L;
	L = " " + L + "*";
	while (M--) {
		int x, y; cin >> x >> y;
		G[x].emplace_back(y);
		G[y].emplace_back(x);
	}
	
	bfs();
}