※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 28073번 문제인 PSAT 특별과정이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/28073
28073번: PSAT 특별과정
첫 번째 줄에 문제의 개수 $N$ $(2 \le N \le 1\,000\,000)$과 문제의 연결 관계의 수 $M$ $(0 \le M \le \min(1\,000\,000,\cfrac{N(N-1)}{2}))$이 공백으로 구분되어 주어진다. 각 문제는 1번부터 차례대로 $N$번까지 번
www.acmicpc.net
가장 적은 '문제'를 푸는 경로는 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();
}'BOJ' 카테고리의 다른 글
| [BOJ 28214 // C++] 크림빵 (0) | 2023.12.07 |
|---|---|
| [BOJ 17103 // C++] 골드바흐 파티션 (1) | 2023.12.06 |
| [BOJ 28072 // C++] K512에서 피자 먹기 (0) | 2023.12.04 |
| [BOJ 28071 // C++] 승형이의 사탕 사기 (2) | 2023.12.03 |
| [BOJ 28070 // C++] 유니의 편지 쓰기 (1) | 2023.12.02 |