백준 16940번, BFS 스페셜 저지 풀이

문제

백준 16940번

풀이

이러한 트리를 BFS, 너비 우선 탐색으로 순회한 결과가 올바른 것인지 아닌지 출력해야 합니다.

이 과정이 올바르다면, 아래의 조건을 만족할 것입니다.

 

1) 각 노드의 깊이는 오름차순 형태이다.

2) 부모 노드가 들어온 순서대로 자식 노드들 간의 순서가 결정된다.

 

2번째 조건이 말로 하면 어려우니, 아래 예제를 참고해주세요.

 

위 예제 사진에서는,

 

깊이가 0(루트 노드)인 노드는 1,

깊이가 1인 노드는 2와 3,

깊이가 2인 노드는 4입니다.

 

아래와 같이 순회했다고 가정합시다.

1 2 3 4

1번째 조건에서, 각 노드들의 깊이를 배열로 나타내면, [0, 1, 1, 2]이므로 오름차순을 만족합니다.

2번째 조건에서, 각 노드들의 부모 노드는 (루트 노드 제외) [1, 1, 2]가 됩니다. 역시 부모 노드의 방문 순서 그대로 자식 노드들이 등장합니다.

 

이번엔 1번째 조건을 위반하는 순회 방식입니다.

1 2 4 3

로 순회를 한다면, 1번째 조건에서 각 노드의 깊이를 나타내면, [0, 1, 2, 1]로 오름차순이 아니므로 올바른 BFS 순회가 아닙니다.

 

다음은 2번째 조건을 위반하는 순회 방식입니다.

1 3 2 4 5 6 7

위 순회는

1번째 조건에서는 노드의 깊이가 [0, 1, 1, 2, 2, 2, 2]로 만족합니다.

하지만, 2번째 조건에서 각 노드의 부모가(루트 노드 제외) [1, 1, 2, 2, 3, 3]와 같습니다.

1번째 노드의 자식 방문 순서를 3을 먼저 보았기 때문에, 3의 자식들이 먼저 나와야 합니다. 따라서, 틀린 순회 과정입니다.

 

2번째 조건은 자료구조 큐를 활용하여 쉽게 구현할 수 있습니다.

 

또한, 각 노드의 depth(깊이)와 부모를 구해두는 과정은 순 BFS 또는 DFS를 활용하여 구할 수 있습니다.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef unordered_map<int, int> mpii;

vi graph[100001], depth, parent;

void dfs(int a, int d) {
	depth[a] = d++;
	for (const auto &nxt : graph[a]) if (depth[nxt] > d) dfs(nxt, d), parent[nxt] = a;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	depth.assign(n + 1, 1e9);
	parent.assign(n + 1, 1e9);
	parent[1] = 1;
	for (int i = 0; i < n - 1; i++) {
		int a, b; cin >> a >> b;
		graph[a].emplace_back(b);
		graph[b].emplace_back(a);
		if (a == b) {
			cout << "0";
			return 0;
		}
	}
	dfs(1, 1);
	int prv = 0;
	queue<int> par, tmp;
	while (n--) {
		int a; cin >> a;
		if (prv > depth[a]) {
			cout << "0";
			return 0;
		}
		if (prv != depth[a]) par = tmp, tmp = {};
		tmp.push(a);
		if (a == 1) continue;
		int p = parent[a];
		while (!par.empty() && par.front() != p) par.pop();
		if (par.empty()) {
			cout << "0";
			return 0;
		}

		prv = depth[a];
	}

	cout << "1";
}