[백준] No.11437 - LCA (C++, 최소 공통 조상)
문제
https://www.acmicpc.net/problem/11437
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
풀이
solved.ac 난이도: Gold 3
트리에 속한 두 노드의 최소 공통 조상(Lowest Common Ancestor)을 찾는 문제이다.
동일한 문제이지만 입력의 수가 더 많고 시간제한이 짧은 LCA 2와는 다르게 단순히 구현해도 시간안에 해결할 수 있다.
일단 LCA2를 푸는 기초가 되는 풀이를 살펴보자.
두 노드는 어느 곳에 위치하든 조상 노드로 한 칸씩 위로 올라가다 보면 서로 공통된 조상을 찾을 수 있다.
이때 최소 공통 조상의 위치는 공통 조상 중 가장 트리에서의 높이(heigt)가 높은(루트의 높이를 0이라 할 때) 노드라 할 수 있다.
따라서 a와 b노드의 LCA를 찾고 싶다면 일단 두 노드의 높이를 갖도록 맞추어 준다.
만일 a가 더 높이가 높다면 조상 노드로 한칸씩 이동하며 b노드의 높이와 맞추어준다.
높이를 맞추었다면 두 노드를 조상 노드로 한 단계씩 높여가며, 동일한 조상 노드가 발견된다면 해당 노드가 LCA가 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
Node* FindLCA(Node* a, Node* b){
Node* p1 = a;
Node* p2 = b;
if(a->height != b->height){ //높이가 다르면 같아지게 만듬
if(a->height < b->height){ //p1은 더 높이가 큰 경우
p1 = b;
p2 = a;
}
while(p1->height != p2->height)
p1 = p1->parent;
}
while(p1 != p2){
p1 = p1->parent;
p2 = p2->parent;
}
return p1;
}
|
cs |
해당 알고리즘은 한 단계씩 조상 노드로 이동하므로 LCA가 p1의 k번째 조상이라면 O(k)의 시간 복잡도를 갖는다.
따라서 LCA 2와 같이 입력이 크고 시간 제한이 있는 문제에서는 시간 초과가 발생할 수 있다.
코드
| #include <iostream> | |
| #include<vector> | |
| using namespace std; | |
| class Node{ | |
| public: | |
| int num, height; | |
| Node* parent; | |
| vector<Node*> links; | |
| void AddLinks(Node* link){ | |
| links.push_back(link); | |
| } | |
| void SetParentAndHeight(Node* par, int h){ | |
| parent = par; | |
| height = h; | |
| for(int i=0; i<links.size() ; ++i){ | |
| if(links[i] != par) | |
| links[i]->SetParentAndHeight(this, h+1); | |
| } | |
| } | |
| }; | |
| int node_num; | |
| vector<Node> tree; | |
| Node* FindLCA(Node* a, Node* b){ | |
| Node* p1 = a; | |
| Node* p2 = b; | |
| if(a->height != b->height){ //높이가 다르면 같아지게 만듬 | |
| if(a->height < b->height){ //p1은 더 높이가 큰 경우 | |
| p1 = b; | |
| p2 = a; | |
| } | |
| while(p1->height != p2->height) | |
| p1 = p1->parent; | |
| } | |
| while(p1 != p2){ | |
| p1 = p1->parent; | |
| p2 = p2->parent; | |
| } | |
| return p1; | |
| } | |
| int main(){ | |
| ios_base::sync_with_stdio(0); | |
| cin>>node_num; | |
| tree = vector<Node>(node_num+1); | |
| for(int i=1; i<=node_num ; ++i) | |
| tree[i].num= i; | |
| int a,b; | |
| for(int i=0 ; i<node_num-1 ; ++i ){ | |
| cin>>a>>b; | |
| tree[a].AddLinks(&tree[b]); | |
| tree[b].AddLinks(&tree[a]); | |
| } | |
| tree[1].SetParentAndHeight(nullptr, 0); | |
| int pair_num; | |
| cin>>pair_num; | |
| while(pair_num--){ | |
| cin>>a>>b; | |
| cout<<FindLCA(&tree[a], &tree[b])->num<<'\n'; | |
| } | |
| return 0; | |
| } |