[백준] 3584번 : 가장 가까운 공통 조상 (C++)

3584번 : 가장 가까운 공통 조상

---

 

문제)

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

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

 

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

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

 

 

입력 :

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

 

 

 

출력 :

각 학기에 대해 근우의 총 학점과 평점(GPA)을 출력한다. 정답과의 절대 오차는 10-1까지 허용한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int t, n;
int parent[10010];
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> t;
 
    for (int _ = 0; _ < t; _++)
    {
        cin >> n;
 
        // 다음 t를 위해 배열 초기화
        fill(parent, parent + 10010, 0);
 
        // 자식 노드로는 내려갈 필요가 없으므로.
        // 부모 노드만 체크한다.
        int a, b;
        for (int i = 0; i < n - 1; i++)
        {
            cin >> a >> b;
            parent[b] = a;
        }
 
        // 두 노드의 부모를 저장할 배열
        vector<int> temp1;
        vector<int> temp2;
 
        int x, y;
        cin >> x >> y;
 
        // 두 노드의 부모 노드들을 각 배열에 저장한다.
        while (x != 0)
        {
            temp1.push_back(x);
            x = parent[x];
        }
 
        while (y != 0)
        {
            temp2.push_back(y);
            y = parent[y];
        }
 
        // 맨 뒤 인덱스부터 두 배열이 달라지는 인덱스를 찾는다.
        int idx1 = temp1.size() - 1;
        int idx2 = temp2.size() - 1;
 
        while (idx1 >= 0 && idx2 >= 0 && temp1[idx1] == temp2[idx2])
        {
            idx1--;
            idx2--;
        }
 
        cout << temp1[idx1 + 1] << "\n";
 
    }
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/3584 

3584번: 가장 가까운 공통 조상