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

문제 링크입니다. https://www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

BFS의 순서를 확인할 수 있는지를 물어보는 문제였습니다.

1번부터 BFS 탐색을 시작했을 때, 주어진 순서가 올바른 BFS 방문 순서인지를 확인하는 문제입니다.

부모가 같은 노드가 다수일 경우, 방문 순서가 여러개가 나올 수 있습니다.

문제 예시에서는 (1, 2, 3, 4) or (1, 3, 2, 4)가 나올 수 있습니다. 

여러개가 나올 수 있는 방문 순서 중 하나가 입력에 주어졌는지를 찾아야합니다.

 

나올 수 있는 모든 경우를 확인하는 방법보다는 문제에서 나온 경우만을 맞는지 확인하는 것이 효율적입니다.

 

 BFS 탐색 중에서 다음 노드를 찾는 방법은 

        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 0){
                check[xx] = 1;
                q.push(xx);
            }
        }

탐색하려는 점과 연결된 점을 vector의 처음부터 끝까지 찾아보는 방법입니다.

 

그렇다면, 탐색하는 순서를 문제에서 주어진 순서대로 탐색하게 하면 된다라는 결론이 나옵니다.

 

 

저는 order라는 배열을 사용해서 X번 정점이 몇번 째에 탐색되는 지를 저장했습니다.

 

connect 백터를 통해 X번 정점이 어떤 정점과 연결괴어 있는지를 저장한 뒤, order 배열에 저장된 값을 통해 정렬을 했습니다.

-> 문제에서 주어진 순서대로 정렬을 할 수 있게 합니다.

 

해당 과정을 거친 뒤, BFS의 탐색 순서가 주어진 순서와 맞는지 확인해주면 됩니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N;
vector<int> connect[100001];
int check[100001];
int order[100001];
int Bfs_order[100001];

bool cmp(int x, int y){
    if(order[x] < order[y]) return true;
    else return false;
}

void bfs(){
    queue<int> q;
    q.push(1);
    check[1] = 1;
    int cnt = 1;
    while(!q.empty()){
        int x = q.front();
        Bfs_order[x] = cnt++;
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 0){
                check[xx] = 1;
                q.push(xx);
            }
        }
    }
}

bool check_order(){
    for(int i = 1; i <= N; i++){
        if(Bfs_order[i] != order[i]) return false;
    }
    return true;
}


void solve(){
   for(int i = 1; i <= N; i++){
       sort(connect[i].begin(), connect[i].end(), cmp);
   }
   bfs();
   if(check_order()) cout << "1";
   else cout << "0";
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 1; i < N; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    for(int i = 1; i <= N; i++){
        int x;
        cin >> x;
        order[x] = i;
    }
    solve();
    return 0;
}​

 

 

질문 및 조언은 댓글 남겨주세요