[백준/C++] 가장 가까운 공통 조상 (No. 3584)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 트리가 주어지면 특정 노드들 간의 공통조상을 구하면 되는 문제다.

 

처음부터 자식노드와 부모노드를 알려주기 때문에, 두 노드 a, b 의 공통조상을 구하기는 쉽다.

왜냐하면 두개의 노드를 따라서 부모노드를 찾아가면 공통 조상들을 찾을 수 있기 때문이다.

 

여기서 우리는 가장 가까운 공통 조상을 찾아야한다.

 

가장 가까운 공통 조상을 찾는 방법도 간단하다.

 

먼저 a 노드에서 출발해 최상위 조상까지 올라가며 어떤 노드가 a 노드의 조상인지 파악한 뒤 방문 처리를 한다.

그러면 이제 b에서 출발해 조상을 찾아가며 처음으로 만나는 a에서 이미 방문한 노드가 가장 가까운 공통 조상이다.

 

이 과정이 b에서 처음 만나는 a 와의 공통조상을 찾았기 때문에 a와 b에 가장 가까운 공통조상임을 알 수 있다.

 

 

​

[아이디어 정리]

1. a 노드에서 시작해 최상위 부모노드를 만날 때 까지 a노드의 부모노드를 찾으며 방문처리를 한다.
2. b 노드에서 최상위 부모노드를 찾아가며 a가 방문한 적이 있는 부모노드가 나오면 그 노드가 a와 b노드의 가장 가까운 조상이다.

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int tc;
    cin >> tc;
    for (int TC = 0; TC < tc; TC++) {
        int N; 
        cin >> N;
        int st, ed;
        vector<int> parents(N + 1, 0);
        vector<bool> visited(N + 1, false);
        //vector<vector<int>> graph(N + 1);
        
        for (int i = 1; i < N; i++) {
            cin >> st >> ed;
            parents[ed] = st;
        }
        int a, b;
        cin >> a >> b;
        int nextP=a;
        while (nextP) {
            visited[nextP] = true;
            nextP = parents[nextP];
        }
        nextP = b;
        while (nextP) {
            if (visited[nextP]) {
                cout << nextP << "\n";
                break;
            }
            nextP = parents[nextP];
        }
    }
    return 0;
}

 

---

정말 오랜만에 알고리즘 문제를 풀었는데, 다행히 쉬운문제였다.

다시 알고리즘을 시작하고 싶은데... 시간이 잘 안난다 ㅠㅠ

 

https://www.acmicpc.net/source/81923247