문제 요약 및 풀이
트리가 주어지고, 노드들을 탐색한 순서가 주어진다. 이때, 탐색한 순서가 BFS 탐색으로 가능한 순서가 맞는지 검증하면 된다.
처음에는 정말 단순하게 접근했다.
그냥 BFS 탐색을 한번 돌면서, level graph를 만들고, level graph 상에서의 level이 비내림차순으로 배치되었는가만 봤다.
하지만, 역시나 바로 WA를 받았다. (생각을 좀 하고 풀라고…)
문제가 뭘까 생각중에 아래 예제를 질문 게시판에서 봤다.
이 경우에는 12354 또는 13245만 가능한데, 2 또는 3을 방문하는 순서에 따라 4 와 5의 방문순서가 결정되기 때문이다. 따라서, 12345와 같은 방문 순서가 불가능해진다.
그렇기 때문에 위에서 생각한 level graph로 판단하는 건 불가능하다.
그래서 결국 주어지는 순서대로 BFS 방문을 직접 해보는데, 다음노드로 넘어갈 때의 순서를 주어진 순서를 참고하여 탐색해보는 방법을 사용했다.
풀이 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s,n) for(int j = s; j < n; j++)
using namespace std;
typedef pair <int, int> pii;
int N;
vector<int> edges[110000];
int order[110000];
bool chk[110000];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
for1(0, N - 1) {
int a, b;
cin >> a >> b;
edges[a].push_back(b);
edges[b].push_back(a);
}
for1(0, N) {
int a;
cin >> a;
order[a] = i;
}
queue<int> Q;
Q.push(1);
int crt = 0;
while(!Q.empty()) {
int f = Q.front(); Q.pop();
if(crt != order[f]) {
cout << 0;
return 0;
}
chk[f] = true;
crt++;
vector <pii> v;
for(int nxt : edges[f]) {
if(chk[nxt]) continue;
v.push_back({ order[nxt], nxt });
}
sort(v.begin(), v.end());
for(auto nxt : v) {
Q.push(nxt.second);
}
}
cout << 1;
}