BFS 스페셜 저지 (BOJ 16940)

문제

이미지 클릭

문제 설명

• BFS를 활용한 탐색 순서를 파악하는 문제이다.
• n개의 정점에 대해서 n-1개의 간선을 가지고 있다.
• 아래의 그림에서는 1-3-2-4로 탐색을 하거나 1-2-3-4로 탐색할 수 있기 때문에 기존 BFS방식만 사용하면 안 된다.

문제 접근

1. BFS: 기존과 같게 BFS를 탐색하는 코드를 만들어줌.
2. 정렬: 각 정점에서 연결되는 다른 정점을 v [ (현제 정점) ].push_back( (다음 정점) )을 해줄 때에 (다음 정점)들은 정렬되지 않고 들어온 순서대로 저장되기 때문에 1-2-3-4와 1-3-2-4와 같은 순서를 파악할 수 없기 때문에 v[ (현제 정점) ]을 정렬해 줄 필요가 있다.

최종 코드

#include <iostream>
#include <vector>
#include <queue>
#include<algorithm>
using namespace std;
vector<int> v[100004];
vector<int> v1;
int d[100004];
bool visited[100004];
bool f(int n) {
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        if (v1[cnt] != x) return 0;
        cnt+=1;
        for (int i : v[x]) {
            if (!visited[i]) {
                visited[i] = 1;
                q.push(i);
            }
        }
    }
    return 1;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    v1.resize(n+4);
    for (int i = 0; i < n; i++) {
        cin >> v1[i];
        d[v1[i]] = i;
    }
    for (int i = 1; i <= n; i++) sort(v[i].begin(), v[i].end(), [](int a, int b) {return d[a] < d[b];});
    if (f(n)) cout << 1;
    else cout << 0;
}

 

코드에서 볼 필요가 있는 부분은 정렬하는 과정인데 제일 먼저 v1에 방문 순서를 저장해 준 다음에 

d [ (방문할 정점) ] = 순서 

 

위와 같은 방식으로 d에 저장해 준다.

for (int i = 0; i < n; i++) {
        cin >> v1[i];
        d[v1[i]] = i;
}

 

앞의 과정을 실행한 다음에 v [ (정점) ]을 다음과 같이 정렬해 준다.

sort(v[i].begin(), v[i].end(), [](int a, int b) {return d[a] < d[b];});

 

예를 들어서 다음과 같이 입력을 받았다고 하자.

4
1 2
1 3
2 4
1 3 2 4

 

위와 같은 방식으로 입력받는다면 v에는 다음과 같이 입력을 받게 될 것이다.

v[1]={2,3}
v[2]={1,4}
v[3]={1}
v[4]={2}

 

이 방식으로 BFS로 탐색해 준다면 1-2-3-4의 방식으로 탐색 결과가 일반적으로 나오기 때문에 우선순위를 정해주어야 한다.

d[0]=1
d[1]=3
d[2]=2
d[3]=4

 

이런 방식으로 d에 지정해 주고 다음과 같은 방법으로 정렬을 해준다.

//v[1]로 예시 들기
v[1]={2,3}

//d에 저장해둔 2,3의 순서 불러오기
d[2]=2,d[3]=1

//!오름 차순 정렬
d[3]<d[2] -> v[1]={3,2}

 

위와 같은 방식으로 연결되어 있는 모든 정점을 정렬해 준다.

 

이미지 클릭