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

문제 링크: www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

1. 주의할 점

- 입력의 시작으로 1이 들어오는지 확인한다

- 2-2번의 조건을 정확히 처리한다

 

2. 구현

- 모든 간선에 대한 정보를 V[] 벡터에 저장한다

- 입력 받는 경로를 Order 벡터에 저장한다

- Finish[] 배열을 통해 방문했는지 체크한다

- inQueue[] 배열을 통해 현재 Queue에 있는지 확인한다

- Cnt를 통해 현재 비교해야 하는 번호를 가라킨다(Order[cnt])

- 큐에 1을 넣고 BFS를 시작한다. While문의 종료 조건으론 Queue가 비었거나 불가능한 경우다

- 현재 정점에서 방문하지 않은 모든 정점을 표시한다. CC: 추가된 정점의 수

- Cnt~Cnt+CC-1까지 Order[] 배열을 확인하여 현재 Queue에 존재하는지 표시한다. 만약 존재한다면 inQueue[]의 값을 false로 전환하고 큐에 추가한다. 존재하지 않다면 Avail을 False로 전환한 후, 종료한다

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
bool finish[100001]={false,};
bool inQueue[100001]={false,};
int node,a,b,cnt=1,len;
vector<int> v[100001];
vector<int> order;
bool avail=true;

bool check(){
    for(int i=cnt;i<cnt+len;i++){
        if(!inQueue[order[i]]) return false;
        else inQueue[order[i]]=false;
    }
    cnt+=len;
    return true;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node;
    for(int i=0;i<node-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i=0;i<node;i++){
        cin>>a;
        order.push_back(a);
    }
    queue<int> q;
    q.push(1);
    finish[1]=true;
    if(order[0]!=1) avail=false;
    
    while(!q.empty() && avail){
        int cidx = q.front();
        q.pop();
        int cc=0;
        for(int i=0;i<v[cidx].size();i++){
            int next = v[cidx][i];
            if(finish[next]) continue;
            finish[next]=true;
            cc++;
            inQueue[next]=true;
        }
        for(int i=0;i<cc;i++){
            if(inQueue[order[cnt+i]]){
                inQueue[order[cnt+i]]=false;
                q.push(order[cnt+i]);
            }
            else{
                avail=false;
                break;
            }
        }
        cnt+=cc;
    }
    avail ? cout<<1 : cout<<0;
    return 0;
}