[SWEA] 1248 공통조상

출처: SWEA

Approach

노드 [8]의 부모노드는 [5]이며, [13]의 부모노드는 [11]이다.

위로 올라가면 공통 조상격인 [3]과 [1]이 있으며

가까운 공통 조상은 [3]이 된다.

 

가장 가까운 공통 조상노드를 기준으로 하였을 때,

서브트리의 크기는 아래와 같다. (기준 노드를 포함한 수치)

 

① 구조체로 트리(Tree) 구현

- 이진트리이므로 왼쪽/오른쪽 자식노드를 순차적으로 구성

- 공통 조상을 탐색하기 위해 부모노드 표시

 

② 첫번째 대상 노드를 시작으로 부모 노드(들) 표시

ex) 정점 [8]에 대해서 [5] → [3] → [1] 노드들이 vistied[] 표시된다.

 

③ 두번째 대상 노드를 시작으로 조상 노드 추적

ex) [13]을 기준으로 조상 노드를 추적할 때, [11] → [6] → [3] → [1] 으로 진행될테지만

      추적 중간에 첫번째 노드 대상으로 이미 표시했던 [3]에 중복 방문(추적)하여

      가까운 공통 조상임을 알 수 있다.

 

④ 찾은 공통 조상으로 서브트리 크기 확인

- 공통 조상 노드도 크기에 포함된다.

- 완전이진 트리 구성은 아니기 때문에 왼쪽/오른쪽 자식 노드 존재 여부 확인

- 자식이 존재한다면 재귀적으로 탐색 (DFS)

 

DFS (depth-first search, 깊이 우선 탐색) 

깊이 우선 탐색(depth-first search, DFS)

---

#include <stdio.h>

const int MAX_V = 1e4 + 2;
struct Node {
    int parent, left, right;
    void init()
    {
        parent = left = right = 0;
    }
}tree[MAX_V];

int parent, child, cur;
int TC, V, E, tg1, tg2;
bool check[MAX_V];

void init()
{
    for (int i = 0; i < MAX_V; ++i) 
    {
        tree[i].init();
        check[i] = false;
    }
}

void input()
{
    // 정점 개수, 간선 개수
    scanf("%d %d", &V, &E); 

    // 공통 조상을 찾는 두 개의 정점 번호
    scanf("%d %d", &tg1, &tg2); 

    // E 개의 간선 정보
    for (int i = 0; i < E; i++) {
        scanf("%d %d", &parent, &child);
        // 아직 왼쪽 자식이 존재하지 않는 경우
        if (tree[parent].left == 0)
            tree[parent].left = child;
        // 오른쪽 자식으로 표시
        else 
            tree[parent].right = child;

        // 자식노드에 부모노드 표시
        tree[child].parent = parent;
    }
}

int DFS(int cur) {
    int ans = 1; // 출발 노드 포함

    // 왼쪽 자식 노드를 타고 재귀 탐색 (왼쪽 서브 트리)
    if (tree[cur].left != 0)
        ans += DFS(tree[cur].left);

    // 오른쪽 자식 노드를 타고 재귀 탐색 (오른쪽 서브 트리)
    if (tree[cur].right != 0)
        ans += DFS(tree[cur].right);

    return ans;
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &TC);
    for (int tc = 1; tc <= TC; tc++) {
        init();
        input();

        cur = tree[tg1].parent;
        while (true) {
            check[cur] = true;
            // root 노드에 도달한 경우
            if (cur == 1) break;
            // 부모 노드 거슬러 올라가기
            cur = tree[cur].parent;
        }

        cur = tree[tg2].parent;
        while (true) {
            // tg1 조상 노드 탐색 과정에서 방문한 곳인 경우
            if (check[cur]) {
                // 처음으로 중복방문 되는 곳이 가장 가까운 공통 조상
                // 해당 노드를 기준으로 서브트리 크기 조사
                printf("#%d %d %d\n", tc, cur, DFS(cur));
                break;
            }
            cur = tree[cur].parent;
        }
    }
}