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

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

 

 

이 문제는 그래프의 관계가 주어지고 노드 1부터 시작하여 입력된 순서대로 나올 수 있는지 여부를 출력하는 문제이다.

즉 1번 테스트 케이스를 보면

1 -> 2

1 -> 3

2 -> 4

의 관계가 주어졌을때

1부터 확장한다면 나올 수 있는 순서가

1, 2, 3, 4

1, 3, 2, 4가 나오게 된다.

이외에는 bfs를 수행했을때 나올 수 없는 순서이다.

 

 

따라서 입력된 순서를 기준으로 간선들을 정렬해 주었다.

예를 들어 1번 테케에서

간선의 입력 순서가

1 -> 3

1 -> 2

2 -> 4

가 되고 

나올 수 있는 순서가 1, 2, 3, 4로 입력이 된다고 가정한다면

 

1번 간선에는 3, 2가 저장이 될 것이다

이것을 입력된 순서로 정렬한다면

 1번 간선에는 2, 3순으로 저장이 된다.

따라서 정렬 한 후 1번 노드에서 bfs를 수행한 후 입력된 순서와 맞는지 비교하고 아닐 경우 0을 출력하였다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    string s;
    vector<int> v;
};

int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
int N;
vector<vector<int>> v(100001);
bool visited[100001];
int order[100001];
int bfs_order[100001];

bool cmp(int a, int b) {
    return order[a] < order[b];
}

void bfs(int a) {
    queue<int> q;
    q.push(a);
    visited[a] = true;
    int idx = a;

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        bfs_order[x] = idx++;

        for(auto it : v[x]) {
            if(!visited[it]) {
                q.push(it);
                visited[it] = true;
            }
        }
    }
}

void solve() {
    bfs(1);

    bool isflag = false;
    for(int i = 1; i <= N; i++) {
        if(order[i] != bfs_order[i]) {
            isflag = true;
            break;
        }
    }


    if(!isflag) {
        cout << 1;
    }
    else cout << 0;
}

void input() {
    cin >> N;

    for(int i = 0; i < N-1; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for(int i = 1; i <= N; i++) {
        int a;
        cin >> a;
        order[a] = i;
    }

    for(int i = 1; i <= N; i++) {
        sort(v[i].begin(), v[i].end(), cmp);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}