[코드트리/C++] 조상 노드 (DFS)

문제

https://www.codetree.ai/problems/node-ancestor/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

구상

조상 노드의 유무를 파악하는 문제였다. 오랫만에 찐 dfs다운 문제를 만나서 잠깐이지만 좀 설렜다 ㅎㅎ 조상 노드의 유무를 파악하는 방법이 dfs를 이용하는 것이라는 것만 파악했다면 어렵지 않은 문제인데, 해당 과정이 흔하지 않아 처음 봤을땐 어렵게 느껴졌던 것 같다.

 

dfs 과정을 루트(1번 노드)부터 시작하여 재귀적으로 진행하다보면 이것으로 노드간의 부모 자식 유무를 파악할 수 있을 것 같은 느낌이 든다. 그 느낌이 맞는데, 항상 자식보다는 부모(조상) 노드를 먼저 탐색하게 되기 때문이다. 그런데, 여기서 문제가 되는건, 꼭 해당 노드의 조상 노드가 아니어도 먼저 방문할 수 있다는 점이다. 그래서 여기에 조건을 하나 더 추가해줬다. 바로, 해당 노드의 자식(자손) 노드를 모두 탐색하고 나면 해당 dfs함수가 끝이 나게 되는데, 그 시점 또한 기록하는 것이다. 조상 노드는 자손 노드보다 탐색 시작 시간이 빠르고, 탐색 종료 시간이 늦기 때문이다. 

 

예를 들면, 노드 2번이 노드 6번의 조상인가? 라는 질문에, 노드 2번이 6번에 비해 탐색 시작 시간이 빠르지만, 탐색 종료 시간도 빠르기에 조상이 아니다. 노드 2번은 자신의 마지막 자손 노드 5번의 탐색이 끝나고 나서 탐색이 종료가 되기 때문이다. 노드 6번은 아예 별개의 노드이다. 또한, 노드 1번은 노드 5번에 비해 탐색 시작 시간이 빠르지만, 탐색 종료 시간이 늦다. 그래서 노드 1번은 노드 5번의 조상이다. 이렇게 노드 탐색 시작과 종료 시간을 가지고 조상 노드의 유무를 파악할 수 있다. 

 

풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
/*
조상노드
https://www.codetree.ai/problems/node-ancestor/description
tree의 edge 개수 = node 개수 - 1
*/

int node_num;
int parent; int child;
vector<vector<int>> tree(200001); // = vector<int> tree[200001];
vector<int> entry_time(200001);
vector<int> exit_time(200001);

int entry_t = 0;
int exit_t = 0;

void dfs(int curr_node) {
    entry_time[curr_node] = ++entry_t;

    for (auto children : tree[curr_node]) {
        dfs(children);
    }

    exit_time[curr_node] = ++exit_t;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> node_num;
    for (int i = 0; i < node_num - 1; i++) {
        cin >> parent >> child;
        tree[parent].push_back(child);
    }

    // 로직
    dfs(1); // root(1) 노드

    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> parent >> child;
        if (entry_time[parent] < entry_time[child] && exit_time[parent] > exit_time[child]) cout << "1 ";
        else cout << "0 ";
    }

    return 0;
}