문제
BOJ에서 정답이 여러가지인 경우에는 스페셜 저지를 사용한다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식이다. 오늘은 스페셜 저지 코드를 하나 만들어보려고 한다.
정점의 개수가 N이고, 정점에 1부터 N까지 번호가 매겨져있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있다.
-
큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다.
-
큐가 비어 있지 않은 동안 다음을 반복한다.
-
큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이 정점을 x라고 하자.
-
x와 연결되어 있으면, 아직 방문하지 않은 정점 y를 모두 큐에 넣는다. 모든 y를 방문했다고 처리한다.
2-2 단계에서 방문하지 않은 정점을 방문하는 순서는 중요하지 않다. 따라서, BFS의 결과는 여러가지가 나올 수 있다.
트리가 주어졌을 때, 올바른 BFS 방문 순서인지 구해보자.
입력
첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 BFS 방문 순서가 주어진다. BFS 방문 순서는 항상 N개의 정수로 이루어져 있으며, 1부터 N까지 자연수가 한 번씩 등장한다.
출력
입력으로 주어진 BFS 방문 순서가 올바른 순서면 1, 아니면 0을 출력한다.
풀이
주어진 방문 순서가 BFS로 가능한지 판정하려면, 그 순서를 기준으로 인접 리스트를 정렬한 뒤 실제 BFS를 한 번 돌려 보면 된다. BFS는 같은 레벨 안에서의 순서가 자유롭기 때문에, 원하는 순서를 우선순위로 넣어 주는 방식이다.
코드에서는 입력으로 받은 방문 순서의 위치를 pos에 저장하고, 각 정점의 인접 정점을 그 순서대로 정렬한다. 그 상태에서 BFS를 돌렸을 때 실제 탐색 순서가 입력 순서와 같다면 가능한 BFS 순서다.
임의의 BFS 순서 검증 문제를 정렬 후 비교 문제로 바꾼 것이다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int n, x, y;
vector<int> v[100001];
int pos[100001];
int order[100001];
bool visited[100001];
int solve(int time, int cnt) {
if (order[1] != 1)
return 0;
queue<int> q;
q.push(1);
visited[1] = true;
int idx = 1;
while (!q.empty()) {
int cur = q.front();
q.pop();
if (cur != order[idx++])
return 0;
for (int nxt : v[cur]) {
if (!visited[nxt]) {
visited[nxt] = true;
q.push(nxt);
}
}
}
return 1;
}
bool compare(const int& a, const int& b) {
return pos[a] < pos[b];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n - 1; i++) {
cin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
cin >> order[i];
pos[order[i]] = i;
}
for (int i = 1; i <= n; i++)
sort(v[i].begin(), v[i].end(), compare);
cout << solve(0, 0) << '\n';
return 0;
}복잡도
- 시간 복잡도: 인접 리스트 정렬과 BFS를 수행하므로 이다.
- 공간 복잡도: 그래프, 순서 배열, 큐를 저장하므로 이다.
마무리
가능한 BFS 순서를 직접 정의하려 하지 말고, 입력 순서를 우선하도록 인접 리스트를 정렬해 보면 된다. 그 결과가 그대로 나오면 정답이다.
