[백준/BOJ] 16940번 BFS 스페셜 저지

www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

처음보는 유형의 BFS 문제였습니다. (다시 풀기)

양방향 그래프를 만들고, 마지막 줄의 BFS의 방문순서를 큐에 저장합니다. 현재 정점과 인접한 정점들을 BFS 탐색하기 전에, set에 넣어주어 아까 큐에 저장했던 방문순서의 front 값이 set에 저장되어있는지 확인하는 것이 포인트입니다.

 

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

vector<int> graph[100001];
queue<int> input; // 입력으로 받은 방문 순서가 저장된 큐
bool visit[100001];

bool BFS(int start) {
    queue<int> q;
    q.push(start);
    visit[start] = true;
    
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        set<int> s;
        
        for(int i = 0; i < graph[now].size(); i++) {
            int next = graph[now][i];
            if(visit[next]) continue;
            s.insert(next);
            visit[next] = true;
        }
        
        for(int i = 0; i < s.size(); i++) {
            int tmp = input.front();
            input.pop();
            if(s.find(tmp) == s.end()) return false;
            else q.push(tmp);
        }
    }
    
    return true;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        int v1, v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        graph[v2].push_back(v1);
    }
    
    for(int i = 0; i < n; i++) {
        int x;
        cin >> x;
        input.push(x);
    }
    
    int start = input.front();
    input.pop();
    
    if(start != 1) { // 시작 정점이 1이 아니라면 올바른 순서 X
        cout << "0";
        return 0;
    }
    
    if(BFS(start)) cout << "1";
    else cout << "0";
}