LCA란.
B형 특강에서, 트리 관련 강의를 들었는데, 이 때 언급된 주제이다.
LCA란 태그를 알고는 있었는데, 이번 기회에 공부하게 되었다.
Lowest Common Ancestor. 최소 공통 조상.
트리에서 임의의 두 노드를 찍었을 때, 두 노드가 만나는 가장 가까운 조상 노드를 구하는 문제이다.
이런 트리가 있다면
1번, 7번 노드의 LCA는 3번 노드가,
6번과 13번 노드의 LCA는 8번 노드가 될 것이다.
이 LCA를 찾는 방법은 뭘까?
LCA 찾기
가장 쉽게 생각나는 방법은, 각 노드마다 부모 노드를 기억해놓고, 두 노드가 찍히면 같아질 때 까지
부모노드를 타고 올라가는것이다. 트리이므로 반드시 공통 조상이 존재함이 보장된다.
탐색 시 중요한 것은 시작 높이를 맞추는 것이다.
위의 사진을 다시 보면, 1,7의 LCA를 찾는다고 했을 때, 1과 7을 동시에 타고 올라가면
3에서 만나야 함에도 엇갈리게 됨을 알 수 있다. 그래서 dfs를 통해 Node에 depth 정보를 기록해,
더 깊이 있는 노드를 같은 레벨에서 탐색을 시작할 수 있도록 해주어야 한다.
https://www.acmicpc.net/problem/11437
Basic한 LCA문제이다. 3초 제한, 5만개 노드에 대해 1만번 LCA 찾기 쿼리가 들어온다.
앞서 설명한 방법은 LCA를 찾는데에 걸리는 시간이 O(N)이 된다.
트리가 오른쪽으로만 계속 붙는 경우를 생각하면 된다.
해당 문제의 경우 쿼리가 1만번이므로, O(MN) = 50000 * 10000 = 5억번 연산을 하게 된다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Tree {
int parent;
int depth;
Tree() : parent(0) {}
};
vector<int> v[50001];
int visited[50001];
Tree tree[50001];
void dfs(int node, int depth) {
if (visited[node]) {
return;
}
visited[node] = 1;
tree[node].depth = depth;
for (int i = 0; i < v[node].size(); ++i) {
if (!visited[v[node][i]]) {
tree[v[node][i]].parent = node;
dfs(v[node][i], depth + 1);
}
}
}
void init() {
dfs(1, 1);
}
int find(int a, int b) {
while (tree[a].depth != tree[b].depth) {
if (tree[a].depth < tree[b].depth) {
b = tree[b].parent;
}
else {
a = tree[a].parent;
}
}
while (true) {
if (a == b) {
return a;
}
b = tree[b].parent;
a = tree[a].parent;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n;
int a, b;
for (int i = 0; i < n - 1; ++i) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
init();
cin >> m;
for (int i = 0; i < m; ++i) {
cin >> a >> b;
cout << find(a, b) << '\n';
}
}
인접리스트로 노드들을 연결해주고,
init()에서 dfs를 통해 노드들 정보를 초기화 한 후
O(MN)에 걸쳐 쿼리를 수행하는, 상당히 오래 걸리는 코드이다.
로직 개선
https://www.acmicpc.net/problem/11438
이번엔 이 문제를 보자.
N과 쿼리가 10만으로 늘었고, 시간제한은 1.5초로 줄어들었다.
앞의 방법으로는 절대 시간 내에 돌 수가 없다.
쿼리가 10만이니까 탐색을 Log(N) 정도에 끝내야 한다는 건 알겠는데, 어떻게 해결할 수 있을까?
자연스럽게 높이를 2씩 어떻게 해볼 수 있지 않을까 하는 생각이 든다.
그래서 나는 높이를 2씩 나누면 어떻게 될 수 있지 않을까? 했지만
아무리 머리를 굴려도 2씩 나눠서는 LCA에서 딱 멈추기가 쉽지 않았다.
DP
그래서 AI 선생님에게 이 문제를 들고갔다.
해결책은, 2^k 위의 Parent를 기록하는 것이다.
그리고 높이를 맞출 때에도, 부모를 찾을때에도 2^k씩 옮겨다니며 처리하는 것이다.
참 기가막힌 방법이라고 생각했다.
높이를 맞출 때에는 하나씩 올리지 말고 2^k단위로 올라가면 결국 두 노드의 depth 차이를
18번안에 맞출 수 있다.
마찬가지로 LCA를 찾을 때에도,
최대 2^17(10만 조금 넘는 수)만큼 위의 노드를 확인한다.
이 때 둘의 2^17이 같다? 그럼 그 아래도 확인해봐야한다.
2^16을 확인해본다. 만약 여기서 parent값이 다르다면,
일단 이동한다. 아직 안합쳐지니까.
이동한 위치에서 각각 다시 15부터 확인해보는 것이다.
2^16만큼 이동했고, 2^17은 이미 확정적으로 LCA임이 보장되었으므로
남은 2^16구간을 다시 확인해야한다.
따라서 17부터 보는게 아니고 15부터 확인하면 된다.
이런식으로, 2^0까지 확인해보면 된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct Tree {
int parent[18];
int depth;
Tree() : parent(), depth(0) {}
};
vector<int> v[100001];
int visited[100001];
Tree tree[100001];
void dfs(int node, int depth) {
if (visited[node]) {
return;
}
visited[node] = 1;
tree[node].depth = depth;
for (int i = 0; i < v[node].size(); ++i) {
int next = v[node][i];
if (!visited[next]) {
tree[next].parent[0] = node;
dfs(v[node][i], depth + 1);
}
}
}
int find(int a, int b) {
while (tree[a].depth != tree[b].depth) {
if (tree[a].depth > tree[b].depth) {
int diff = tree[a].depth - tree[b].depth;
int step = 1;
while ((1 << step) <= diff) {
++step;
}
--step;
a = tree[a].parent[step];
}
else {
int diff = tree[b].depth - tree[a].depth;
int step = 1;
while ((1 << step) <= diff) {
++step;
}
--step;
b = tree[b].parent[step];
}
}
if (a == b) {
return a;
}
for (int i = 17; i >= 0; --i) {
if (tree[a].parent[i] != tree[b].parent[i]) {
a = tree[a].parent[i];
b = tree[b].parent[i];
}
}
return tree[a].parent[0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n;
int a, b;
for (int i = 0; i < n - 1; ++i) {
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
dfs(1, 1);
for (int k = 1; k < 18; ++k) {
for (int i = 1; i <= n; ++i) {
if (tree[i].parent[k - 1]) {
tree[i].parent[k] = tree[tree[i].parent[k - 1]].parent[k - 1];
}
}
}
cin >> m;
for (int i = 0; i < m; ++i) {
cin >> a >> b;
cout << find(a, b) << '\n';
}
}
후기
LCA를 처음 공부해봤는데, 재미있는 알고리즘이였다.
특히 지수 단위로 올라가는 아이디어가 참신하다고 느꼈다.
두 노드가 바로 이어진 부모-조상인 경우의 예외처리에서 WA,
dfs내부에서 parent 배열 채우는 부분에서 TLE를 받았다.
