https://www.acmicpc.net/problem/16940
4
1 2
1 3
2 4
1 3 2 4
1 3 2 4
이다.order
배열을 도출할 수 있다.1 | 2 | 3 | 4 |
---|---|---|---|
1 | 3 | 2 | 4 |
order
배열의 값에 따라 오름차순으로 바꾼다.[기존]
1: 2, 3
2: 4
3:
4:
[변경]
1: 3, 2
2: 4
3:
4:
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N;
vector<int> graph[100000];
bool check[100000];
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
// [과정1]: 그래프의 무방향 간선을 입력받는다.
for (int i = 0; i < N - 1; ++i) {
int s, e; cin >> s >> e;
graph[s - 1].push_back(e - 1);
graph[e - 1].push_back(s - 1);
}
// [과정2]: 검증할 사용자의 BFS 순회값을 입력받고 그 순서를 계산한다.
vector<int> userAnswer(N), order(N);
for (int i = 0; i < N; ++i) {
cin >> userAnswer[i];
userAnswer[i]--;
order[userAnswer[i]] = i;
}
// [과정3]: 계산한 순서에 따라 그래프의 인접리스트 순서를 바꿔준다.
for (int i = 0; i < N; ++i)
sort(begin(graph[i]), end(graph[i]), [&](const int& lhs, const int& rhs) {
return order[lhs] < order[rhs];
});
// [과정4]: 이제 만들어진 그래프를 BFS 탐색하고 사용자의 답과 비교한다.
vector<int> bfsAnswer;
queue<int> q;
q.push(0); // BFS 시작 0번 정점 입력.
check[0] = true;
while (!q.empty()) {
int cv = q.front(); q.pop();
bfsAnswer.push_back(cv);
for (const int& nv : graph[cv])
if (!check[nv]) {
check[nv] = true;
q.push(nv);
}
}
if (userAnswer == bfsAnswer) cout << "1\n";
else cout << "0\n";
}