[ 백준 BOJ ] 16940번 - BFS 스페셜 저지 (C++)

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

 

생각 흐름

• 핵심은 특정 단계에 2, 3이 있고, 2 -> 3 순서로 큐에서 뺀다 쳤을 때, 다음 단계는 2와 연결된 것이고 그 다음 단계는 3과 연견될 것이 이다.
• 먼저, 사용한 자료구조 형태는 vector<set<int>> vs; 형태이다. vs[단계]로 해당 단계에 빼줘야 할 set을 가져온다.
• 따라서 input을 돌면서 input[i]에 대해 현재 단계에 존재하는지 검증해준다. 만약 없으면 현재 단계의 존재하는 것을 모두 빼줬는지 검사해준다. 모두 빼줬으면 다음 단계로 넘어가고, 아니라면 0을 출력해준다. 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

int N;
vector<int> edge[100001];
vector<int> input;

vector<set<int>> vs;
bool checked[100001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin>>N;
    for(int i = 0; i<N-1; i++){
        int a, b;
        cin>>a>>b;
        
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    for(int i = 0; i<N; i++){
        int a;
        cin>>a;
        
        input.push_back(a);
    }
    
    checked[1]=true;
    set<int> s;
    for(auto i : edge[1]){
        s.insert(i);
        checked[i]=true;
    }
    vs.push_back(s);
    
    int inputPosition = 1;
    int vsPosition = 0;
    while(inputPosition<input.size()){
        int cnt = (int)vs[vsPosition].size();
        for(; inputPosition<input.size(); inputPosition++){
            auto iter = vs[vsPosition].lower_bound(input[inputPosition]);
            if(iter==vs[vsPosition].end()||*(iter)!=input[inputPosition]){
                if(cnt>0){
                    cout<<0<<endl;

                    return 0;
                }
                vsPosition++;
                break;
            }
            checked[*(iter)]=true;
            cnt--;
            set<int> s;
            for(auto a : edge[*(iter)]){
                if(checked[a]) continue;
                s.insert(a);
            }
            if(!s.empty()) vs.push_back(s);
        }
    }
    
    cout<<1<<endl;
    
    return 0;
}