[SWEA/C++] 공통조상(1248번)

1. 문제 개요

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD 

SW Expert Academy

※ 본 문제는 SW Expert 아카데미의 문제이므로 무단으로 복제 X

1-1. 설명

이진 트리에서 임의의 두 정점 공통 조상 중 가장 가까운 것을 찾으려한다. 

이진트리 예시

위와 같이 임의의 이진트리가 주어지고 두 정점이 명시될 때 이들의 공통조상 중 가장 가까운 정점을 찾고, 그 정점을 루트로하는 서브 트리의 크기를 알아내는 프로그램을 작성해라. 입력에서 주어지는 두 정점이 서로 조상과 자손관계인 경우는 없다. 

1-2. 제한 사항

 - 첫줄은 전체 테스트케이스의 수, 10개가 주어짐

 - 각 케이스의 첫줄은 정점의 수, 간선의 수, 공통 조상을 찾는 두 개의 정점 번호

 - 정점의 수는 10 이상 10000 이하

 - 그 다음 줄에는 간선 수만큼의 정점이 주어지며, "부모 자식" 순서로 표기

---

2. 구현

2-1. 풀이

정점을 저장한 Node를 구성해주고, 부모와 각각의 자식을 저장할 수 있게끔 하였다. 간선의 수만큼 for문을 돌려 정점과 그에따른 부모 및 자식을 저장해주고, 각각의 조상을 저장하는 배열을 선언해 저장해준다. 후에 동일한 공통 조상을 for문을 통해 찾고, 찾은 공통 조상을 재귀를 통해 개수를 구해준다. 

2-2. 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;

constexpr size_t MAX_NODE = 10001;

struct Node {
    int key;
    Node* left;
    Node* right;
    Node* parent;
};

void parentSearch1(Node* node);
void parentSearch2(Node* node);
int equalElementSearch();
void countSubTree(Node* node);

Node node_pool[MAX_NODE];

Node* newNode(int x) {
    node_pool[x].key = x;
    node_pool[x].left = nullptr;
    node_pool[x].right = nullptr;
    node_pool[x].parent = nullptr;
    return &node_pool[x];
}

// 루트 노드를 가리키는 포인터
Node* root;
int parentV1[MAX_NODE], parentV2[MAX_NODE];
int index1 = 0, index2 = 0, countTree = 0;

void init() {
    memset(parentV1, 0, sizeof(parentV1));
    memset(parentV2, 0, sizeof(parentV2));
    memset(node_pool, 0, sizeof(node_pool));
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T, V ,E ,V1, V2 ,A ,B;
    cin >> T;
    for (int test_case = 1; test_case <= T; ++test_case) {
        init();
        cin >> V >> E >> V1 >> V2;
        for (int i = 0; i < E; i++) {
            cin >> A >> B;
            if (node_pool[A].key == NULL) newNode(A); // A 노드 저장
            if (node_pool[B].key == NULL) newNode(B); // B 노드 저장

            if (node_pool[A].left == nullptr) node_pool[A].left = &node_pool[B]; // 왼쪽 연결
            else if (node_pool[A].right == nullptr) node_pool[A].right = &node_pool[B]; // 오른쪽 연결
            node_pool[B].parent = &node_pool[A]; // 부모 연결
        }
        
        index1 = 0, index2 = 0, countTree = 0;
        parentSearch1(&node_pool[V1]); // 첫번째 노드 부모 저장
        parentSearch2(&node_pool[V2]); // 두번째 노드 부모 저장
        int resultNum = equalElementSearch(); // 가장 가까운 공통 조상 찾기
        countSubTree(&node_pool[resultNum]); // 공통 조상을 기준으로 한 SubTree 개수 세기
        cout << '#' << test_case << ' ' << resultNum << ' ' << countTree << "\n";

    }
}

void parentSearch1(Node* node) {
    if (node->key == NULL || node->key == 1) return;
    parentV1[index1++] = node->parent->key;
    if (node->parent != nullptr) parentSearch1(node->parent);
}

void parentSearch2(Node* node) {
    if (node->key == NULL || node->key == 1) return;
    parentV2[index2++] = node->parent->key;
    if (node->parent != nullptr) parentSearch2(node->parent);
}

int equalElementSearch() {
    for (int i = 0; i < index1; i++) {
        for (int j = 0; j < index2; j++) {
            if (parentV1[i] == parentV2[j]) return parentV1[i];
        }
    }
    return 0;
}

void countSubTree(Node* node) {
    countTree += 1;
    if (node->left != nullptr) countSubTree(node->left);
    if (node->right != nullptr) countSubTree(node->right);
}