190215 BOJ 16940번 BFS 스페셜 저지

BFS

- 무방향 그래프의 BFS를 수행하면 된다.

- 가능한 BFS 방문 순서가 여러가지 이므로 신경을 써줄 필요가 있다.

풀이

1. 조건에 따라 큐에 1을 삽입하고 1을 방문처리한다.

2. 큐의 현재 노드에 연결된 다음 노드들을 확인하고 set에 넣어준다.

3. 주어진 BFS 방문 순서대로 확인한다. 이 때, 유효한 노드면 큐에 삽입하고 아니라면 0 출력하고 끝낸다.

4. 방문 순서 배열의 인덱스를 갱신한다.

소스 코드

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

#include <iostream> #include <vector> #include <unordered_set> #include <algorithm> #include <queue> #define FOR(i,a,b) for(int i = a; i < b; i++) #define endl '\n' #define ll long long #define mp(a,b) make_pair(a,b) #define sws ios::sync_with_stdio(false), cin.tie(NULL) #define MAX 200000000 #define pii pair<int, int> using namespace std; vector<int> edge[100002]; queue<int> q; int A[100002], check[100002]; int idx = 1; int N, x, y; int main() {     sws;     cin >> N;     FOR(i, 0, N - 1) {         cin >> x >> y;         edge[x].push_back(y);         edge[y].push_back(x);     }     FOR(i, 0, N) cin >> A[i];     if (A[0] != 1) {         cout << 0;         return 0;     }     q.push(1);     check[1] = 1;     while (!q.empty()) {         int now = q.front();         q.pop();         unordered_set<int> s;         for (int next : edge[now]) {             if (check[next] == 0) {                 s.insert(next);                 check[next] = 1;             }         }         FOR(i, idx, idx + s.size()) {             if (s.count(A[i]) == 0) {                 cout << 0;                 return 0;             }             else q.push(A[i]);         }         idx += s.size();     }     cout << 1; } Colored by Color Scripter

cs