[c++] BOJ 3584 :: 가장 가까운 공통 조상

난이도 : 골드 4

걸린 시간 : 40분

 

문제

가장 가까운 공통 조상 문제 바로가기

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

 

풀이

• b+tree를 vector<int> 출력해서 해결

 

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n;
int head;
vector<vector<int>> childrenList;
vector<int> parentList;

vector<int> findVector(int n) {
    int start = n;
    vector<int> str;
    str.push_back(start);
    while (parentList[start] != 0) {
        start = parentList[start];
        str.push_back(start);
    }

    // 뒤집기 => 제거해도 똑같음
    /*vector<int> res(str.size());
    for (int i = 0; i < str.size(); i++) {
        res[i] = str[str.size() - i-1];
    }*/
    return str;
}

int findCommonParent(int n1, int n2) {
    vector<int> str1 = findVector(n1);
    vector<int> str2 = findVector(n2);
    int minLength = str1.size() < str2.size() ? str1.size() : str2.size();

    int result = head;
    for (int i = 1; i <= minLength; i++) {
        if (str1[str1.size()-i] != str2[str2.size()-i])
            break;
        result = str1[str1.size() - i];
    }
    return result;
}

int main() {
    // 루트부터 해당 노드까지의 path를 string으로 출력
    // 높이(string의 길이)는 깊어봤자 10^4

    int t; cin >> t;
    while (t--) {
        cin >> n;

        // 초기화
        childrenList = vector<vector<int>>(n + 1, vector<int>());
        parentList = vector<int>(n+1);

        for (int i = 0; i < n-1; i++) {
            int s; int e; cin >> s >> e;
            childrenList[s].push_back(e);
            parentList[e] = s; // 부모 노드 저장
        }

        // 루트노드 찾기
        head = 1;
        while (parentList[head] != 0) {
            head = parentList[head];
        }

        int n1, n2; cin >> n1 >> n2; // 찾을 두 노드

        cout << findCommonParent(n1, n2) << '\n';

    }

}

 

개선

• 뒤집기 제거해도 시간 똑같음

 

결과

아이디	메모리	시간	언어	코드 길이
gmldms784	2684	28	C++17 / 수정	1482