알고리즘 :: 백준 :: DFS :: 16940 :: BFS 스페셜 저지

문제

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

문제접근

• 같은 BFS를 수행하더라도, 그래프 인접리스트에 정점이 어떤 순서로 들어가있냐에 따라 순회 순서가 달라질 수 있다.
• 그러나 모든 순회 순서를 고려할 수는 없다.
• 그러므로 주어진 BFS 순회 결과로부터 역으로 순회 순서를 도출한 뒤 다시 BFS를 수행해서 순회 결과와 동일한지 확인해보자!
• 예제를 예로 들어 생각해보자.

4
1 2
1 3
2 4
1 3 2 4

1. 사용자가 입력한 순회 결과는 1 3 2 4이다.
2. 우리는 이 결과로부터 다음 입력순서 order 배열을 도출할 수 있다.

3. 그래프 인접리스트 요소 순서를 order배열의 값에 따라 오름차순으로 바꾼다.

[기존]
1: 2, 3
2: 4
3:
4:
[변경]
1: 3, 2
2: 4
3:
4:

4. 이제 이 그래프 인접리스트를 기반으로 BFS를 수행하고, 사용자가 입력한 순회 결과와 동일한지 검증한다.

코드

#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";
}

결과