BOJ 백준 16964 DFS 스페셜 저지

​​

 

BOJ 백준 16964 DFS 스페셜 저지

문졔: https://www.acmicpc.net/problem/16964

16964번: DFS 스페셜 저지

 

트리와 트리의 노드를 방문한 순서가 주어졌을 때, 올바른 DFS 방문 순서가 맞는지를 구하는 문제이다.

DFS(Depth First Search) 순서를 만족하는 조건을 먼저 생각해봤다.

 

 

1) 직전에 방문한 정점의 자식들 중에서 방문하지 않은 정점의 수가 1 이상일 때

현재 방문 중인 정점이 직전에 방문한 정점의 자식여야 한다. 

 

2) 직전에 방문한 정점의 자식들 중에서 방문하지 않은 정점의 수가 0일 때

현재 방문 중인 정점이 지금까지 방문한 정점들 중에서 방문하지 않은 자식의 수가 1개 이상이면서 가장 최근에 방문한 정점의 자식여야 한다.

 

 

이는 DFS를 실행할 때 방문 중인 정점에 자식이 있으면 그 자식을 따라서 계속 방문하는 특징을 갖기 때문이다. 그림을 보면 이해가 더 쉬울 것이다. 위의 그림을 보면 더 이해가 빠를 것이다.

 

결과적으로 ‘1)번’의 경우는 ‘2)번’의 경우에 속한다고 볼 수 있으므로 ‘2)번’ 과정을 구현한다. 가장 최근에 방문한 정점을 쉽게 찾을 수 있는 자료구조로 스택(stack)이 적절하다.

 

DFS 순서를 만족하면 차례대로 계속 스택에 방문 중인 정점을 push 한다. 방문하지 않은 자식 수가 1 이상이면서 스택의 top에서 가장 가까운 정점이 현재 방문 중인 정점의 부모인지 확인하는데, 만약 아닌 경우가 생기면 이는 올바르지 않은 DFS 순서이다.

 

 

코드로 구현하기 위해 필요한 데이터는 다음과 같다.

 

parent[x]: 정점 x의 부모 정점

childNum[x]: 정점 x의 방문하지 않은 자식 정점 수

x: 현재 방문 중인 정점 번호

 

선행 작업으로 미리 DFS를 사용하여 childNum과 parent 값을 구해주고, 이후 스택을 사용하여 올바른 DFS 순서인지 구한다.

 

#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;


const int N_MAX = 100000;


int n;
int parent[N_MAX + 1];
int childNum[N_MAX + 1];


bool visited[N_MAX + 1];


stack<int> s;
vector<int> order, edges[N_MAX + 1];


void dfs(int x, int prv){
    if (visited[x]) return;
    visited[x] = true;
    parent[x] = prv;
    childNum[prv] += 1;
    
    for (auto next: edges[x]){
        dfs(next, x);
    }
}


int main(){
    scanf("%d", &n);
    
    for (int i = 1; i < n; i++){
        int u, v; scanf("%d %d", &u, &v);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    
    dfs(1, 0);
    
    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        order.push_back(x);
    }
    
    if (order.empty()) {
        printf("0\n"); return 0;
    }


    if (order[0] != 1) {
        printf("0\n"); return 0;
    }
    s.push(order[0]);
    
    bool isPossible = true;


    for (int i = 1; i < n; i++){
        int x = order[i];
        int topIndex = 0;
        while(!s.empty()){
            topIndex = s.top();
            if (childNum[topIndex] > 0) break;
            s.pop();
        }
        if (s.empty()) {
            isPossible = false; break;
        }
        if (parent[x] == topIndex) {
            childNum[topIndex] -= 1;
            s.push(x);
        }
        else {
            isPossible = false; break;
        }
    }
    
    (isPossible) ? printf("1\n") : printf("0\n");


    return 0;
}