백준 16940번 BFS 스페셜 저지

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

16940번: BFS 스페셜 저지

 

 

 

 

 

 

<접근방법>

그래프가 주어지고 bfs를 돌렸을 때, 나올 수 있는 방문 순서인가를 묻는 문제입니다.

방문 깊이?뿐만 아니라 큐에 들어간 순서를 고려해야 합니다.

 

A-a

B-b

 

A, B가 동일 depth이고 a,b가 동일 depth일 때, A가 먼저 큐에 들어갔으면 A, B, a, b가 방문 순서가 되겠지요.

 

q.front()의 결과로 나온 노드의 자식노드가 전부 나왔는가를 확인합니다.

이의 결과로 두 가지가 있습니다.

1. 만약 자식노드가 전부 나왔다.

이 경우는 자식노드를 큐에 넣어주는 순서를 입력받은 순서대로 하여 넣어줍니다.

 

2. 자식노드가 전부 나오지 않았다.

이 경우는 bfs에서 나올 수 없는 케이스므로 bfs를 종료해줍니다.

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
using namespace std;

int A[100002], check[100002];
int idx = 1;
int N, x, y;

vector<int> edge[100002];
queue<int> q;

int main() {
	cin >> N;
	for (int i = 0; i < N-1; i++) {
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}


	if (A[0] != 1) {
		cout << 0;
		return 0;
	}

	q.push(1);
	check[1] = 1;
	set<int> s;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		
		int sz = 0;
		for (int next : edge[now]) {
			if (check[next] == 0) {
				s.insert(next);
				check[next] = 1;
				sz++;
			}
		}

		for(int i=idx; i<idx + sz; i++) {
			if (s.count(A[i]) == 0) {
				cout << 0;
				return 0;
			}
			else q.push(A[i]);
		}
		idx += sz;
	}
	cout << 1;

	return 0;
}