[ BOJ / C++ ] 3584번 : 가장 가까운 공통 조상

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

문제 : https://www.acmicpc.net/problem/3584

---

[  문제  ]

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

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

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

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

[  입력  ]

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

[  출력  ]

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

---

[  문제 접근 및 풀이  ]

LCA 알고리즘과 관련된 문제였지만 LCA 알고리즘을 공부하지 않았던 이유로....

다른 방법으로 풀려고 해보았다.

생각해보니 이 문제는 각 트리마다의 가까운 공통 조상을 구하는 것이니

TLE가 쉽게 나지 않을 거라 생각하고 간선 정보가 들어올 때 자식에 부모를 저장하였다.

두 노드가 주어졌을 때 한 노드를 큐에 넣고 루트노드까지 다 돌면서 방문처리를 해주었고

나머지 노드를 다시 큐에 넣고 방문처리가 되어 있는 노드를 만나면 출력 후 종료 처리 하였다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
void Q_3584();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int T;
    cin >> T;
    while(T--){
        Q_3584();
    }
}
void Q_3584(){
    int N;
    cin >> N;
    vector<int> V[10001];
    for(int i=1;i<N;i++){
        int a,b;
        cin >> a >> b;
        V[b].push_back(a);
    }
    int Node1,Node2;
    bool vis[10001]={false,};
    cin >> Node1 >> Node2;
    queue<int> q;
    q.push(Node1);
    vis[Node1]=true;
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(auto x:V[cur]){
            if(vis[x]) continue;
            vis[x]=true;
            q.push(x);
        }
    }
    while(!q.empty()) q.pop();
    q.push(Node2);
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        if(vis[cur]){
            cout << cur<< "\n";
            return;
        }
        for(auto x:V[cur]){
            q.push(x);
        }
    }
}

---

 

PS. LCA에 대해 잘 써둔 블로그가 있어 공부 할 사람이 있다면 참조하면 좋을 것 같습니다.
https://kibbomi.tistory.com/201

최소 공통 조상 (LCA, Lowest Common Ancestor)(C/C++)