BOJ 16964 - DFS 스페셜 저지 (G3)

사용 알고리즘

DFS

 

풀이

주어진 방문 순서가 DFS의 성질을 만족한다면 DFS라고 볼 수 있을 것이다.

트리에서 DFS의 성질 중 하나는, 어떤 정점을 루트로 하는 서브트리는 그 서브트리상의 모든 정점을 DFS로 방문한다는 것이다. 또한 이 성질은 모든 정점에서 성립하므로, 각 정점에서 이 성질이 성립하는지만 확인하는 것으로 충분하다.

이를 간단하게 확인하는 방법은, 서브트리의 정점 개수와 주어진 순서대로 방문했을 때의 서브트리의 정점 개수가 같은지를 확인하면 된다.

 

이 방법이 왜 가능한지를 생각해보자. 방문 순서가 올바른 DFS가 아니라면 방문 순서가 잘못된 지점이 있을 것이다. 그 지점에서는, DFS를 리프 노드까지 진행하지 않고 중간에 다른 곳으로 이동했을 것이다.



위 그림에서 잘못된 순서인 빨간색 화살표대로 방문하면, 별표친 정점에서의 서브트리를 생략하고 바로 다른 곳으로 이동하므로 별표친 정점에서의 DFS가 끝났을 때, 원래 별표친 서브트리의 정점 개수와 방문 순서대로 방문했을 때의 정점 개수가 달라진다.

순서가 잘못되었다면 이러한 정점이 적어도 하나 존재하므로, 이 알고리즘은 올바로 작동한다.

시간복잡도는 잘 구현하면 O(N)이 가능하다. 아래 코드는 std::set을 이용한 O(NlogN) 구현이다.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
ll n;
ll cur;
bool visited[101010];
set<ll> adj[101010];
ll siz[101010];
ll a[101010];
bool f=1;
ll dfs(ll x){
    visited[x]=1;
    ll ret = 1;
    for(auto next : adj[x]){
        if(!visited[next])ret += dfs(next);
    }
    return siz[x]=ret;
}
void chk(ll x){
    ll cur2 = cur++;
    while(adj[x].find(a[cur]) != adj[x].end()){
        chk(a[cur]);
    }
    if(cur-cur2 != siz[x])f=0;
}
int main(){
    fast;
    cin>>n;
    for(int i = 0 ; i < n-1 ; i++){
        ll a,b; cin>>a>>b;
        adj[a].insert(b);
        adj[b].insert(a);
    }
    for(int i = 0 ; i < n ; i++)cin>>a[i];
    dfs(1);
    if(a[0]!=1)f=0;
    chk(1); cout<<f;
}