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

1. 문제 풀이

 문제 유형은 그래프 탐색 + 이분 탐색 + 재귀입니다. 올바른 경로인지 탐색하는 과정에서 이분 탐색을 응용하기 위해 그래프의 간선 정보를 모두 정렬했고, 그래프 탐색을 하면서 정점의 깊이 값을 할당했습니다. 입력으로 주어진 path에 이 깊이 값을 할당해 깊이가 제대로 정렬되어 있는지 검사하였고, 정렬되어있지 않다면 0을 출력하고 프로그램을 종료했습니다.

 경로가 올바른지 검사하는 로직을 재귀로 구현하기로 결정했고, base condition을 두기 위해 리프 정점의 깊이 값을 전역 변수 mx에 저장했습니다.

 

 is_correct_path(int cur): 정점 cur의 자식들이 정확한 위치에 있는지 검사한다.

 

우선 함수 정의는 위와 같이 결정했습니다. 그런데 cur의 자식 정점들이 path에 어디에 위치해야 하는지 파악하는 과정이 먼저 필요했습니다. 아까 입력으로 주어진 path의 정점의 깊이 값이 정렬되어있는지 사용했던 배열을 통해 각 깊이마다 시작 위치 값을 lower_bound를 사용해 찾을 수 있고, 해당 값들은 탐색을 통해 갱신을 이어가야 하기 때문에 배열에 따로 저장해 두었습니다. 그렇다면 끝 위치는 각 정점의 저장되어 있는 간선의 개수를 통해 파악할 수 있고, 해당 정점에서 탐색이 끝나면 시작 위치에 끝 위치 값을 저장함으로써 순서대로 탐색할 수 있게 됩니다. 각 값을 adj[cur]에서 binary_search로 찾았습니다.

 

< 주의점 >

저는 입력으로 주어진 path를 a[]에 저장했는데, 모든 로직에서 a[0]을 사용했습니다. 문제에서는 시작 정점이 항상 1이라고 설명합니다. 즉 a[0]이 1이 아닌 정점으로 시작하는데 입력으로 주어진 path도 올바른 경우가 있어 WA를 받는 코너케이스가 있습니다. 저도 이것 때문에 계속 맞왜틀을 시전하고 있었습니다...

 

2. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n;
vector<int> adj[100'005];
int a[100'005];

int mx; // max depth
int depth[100'005], chk[100'005], start_idx[100'005];

bool is_correct_path(int cur) {
	// cur이 리프 정점이면 1을 반환(base condition)
    if(depth[cur] == mx) {
        return 1;
    }
	
    // 시작 위치와 끝 위치 값
    int& st = start_idx[depth[cur] + 1];
    int en = st + sz(adj[cur]) - (cur != 1);

    bool ans = 1; // 반환값
    for(int i = st; i < en; i++) {
    	// cur의 자식 정점들이 가지는 범위에서 찾을 수 없는 정점이 있다면 0을 반환
        if(!binary_search(all(adj[cur]), a[i])) {
            return 0;
        }
		// cur의 자식 정점 a[i]에 대해서도 올바른 경로를 가지는지 검사
		ans &= is_correct_path(a[i]);
    }
    st = en; // 시작 위치 값 갱신

    return ans;
}

int main() {
    fastio(nullptr, false);

    cin >> n;
    for(int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    // 경로 입력과, 각 정점의 간선 정보 정렬
    for(int i = 0; i < n; i++) {
        cin >> a[i]; 
        sort(all(adj[i + 1]));
    }
	
    // 너비 우선 탐색을 통해 각 정점의 깊이값 할당
    qi q;
    q.push(a[0]);
    depth[a[0]] = 1;
    while(sz(q)) {
        auto cur = q.front(); q.pop();
        for(auto nxt : adj[cur]) {
            if(depth[nxt]) continue;
            depth[nxt] = depth[cur] + 1;
            q.push(nxt);
        }
    }
	
    // 경로 깊이 값을 chk에 저장, 리프 정점의 깊이 값 mx에 저장
    for(int i = 0; i < n; i++) {
        chk[i] = depth[a[i]];
        mx = max(mx, chk[i]);
    }
	
    // 경로 깊이가 정렬되지 않았거나, 시작 정점이 1이 아닌 경우 0 출력 후 종료
    if(!is_sorted(chk, chk + n) || a[0] != 1) {
        cout << 0;
        return 0;
    }
	
    // 각 깊이의 시작 위치 값 할당
    for(int i = 1; i <= mx; i++) {
        start_idx[i] = lower_bound(chk, chk + n, i) - chk;
    }
	
    // 올바른 경로인지 검사
    cout << is_correct_path(a[0]);
}

 

3. 제출 결과