티스토리 뷰
여러 자료를 참조하면서 LCA를 공부했는데, 어떤 자료는 너무 쉽고 깔끔하지 못하고, 어떤 자료는 난이도가 있고 깔끔하게 설명된 자료였습니다. 그래서 여러 자료를 찾아보며 이해하고, 또 이해하느라 조금 복잡했는데, 하나의 블로그에서 LCA의 개념부터 구현까지 공부할 수 있으면 어떨까 해서 기록을 합니다.
개념에 대해서 알아보고, 백준(BOJ)의 간단한 LCA문제를 풀어보면서 글을 마치겠습니다.
다른 분들에게 도움이 되었으면 좋겠습니다.
1. LCA란?
참조(en.wikipedia.org/wiki/Lowest_common_ancestor)
'In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).'
라고 정의를 하고 있습니다.
(1) Tree 혹은 DAG T에서 정점 v, w의 LCA는 v, w를 자식(descendant, child)으로 하는 가장 깊은(deepest) 노드이다.
(2) 여기서 v가 w의 자식이라면, v와 w의 LCA는 w 자신이 될 수 있다.
(1), (2) 번을 다음 그림으로 설명하면,
정의로는 v, w인데 그림을 보면,, x, y로 되어 있다.
이건 아무 상관없고, 위 그림에서 정점(노드) x, y의 '공통 조상'은 색칠된 노드 전부이고, 그중에서 가장 깊은 것이 진하게 색칠된 노드이고 LCA(최소 공통 조상)이다......(1)
위 그림처럼 y가 x의 자식인 경우 x는 LCA가 될 수 있다......(2)
즉, (1) 번처럼 두 노드의 공통 조상 중에서 깊이가 가장 깊은 노드라고 생각하면 될 것 같습니다.
2. LCA 아이디어
LCA를 구하기 위해서는 몇 변수들이 필요합니다.
당연히 Tree를 저장할 인접 리스트(Adjacency list),
자신의 부모를 저장할 parent배열,
자신의 깊이를 저장할 depth배열이 필요하다.
자, 우선 여기서 단순하게 LCA를 구해봅시다.
두 정점 u, w에서 한 칸씩 위로 올라간 다음(깊이가 높지 않은 방향으로) 두 개가 같아지는 시점이 LCA 아닐까?라고 생각할 수 있다.
위의 방법을 다음과 같은 예에 적용시켜보자.
(화살표의 방향은 LCA를 찾아가는 방향으로 했습니다.)
이런 경우는 LCA를 한번 찾는데 O(n)의 시간을 사용할 것이다. 여기서 n은 Tree에 속한 정점(노드)의 수. 그리고 v가 1칸씩 올라갈 때, 엄청난 수의 정점을 방문하고, LCA인지 체크 or w, v의 깊이가 같은지 체크하고 부모로 올라가기 때문에 시간을 많이 소모할 것이 예상된다.
따라서 이 방법에서 시간 복잡도를 조금 더 줄여볼 방법을 생각해야 한다.
다행히도... O(log n)의 시간에 구할 수 있는 방법이 있다.
그림 3에서 1칸씩 올라갔던 것을 1, 2, 4, 8, 16,... 이런 방법으로 부모를 찾아올라 가는 방법이다.
그래서 위에 정의했던 parent배열이 중요한데,
O(n)의 방식으로 한다면 자기 자신의 바로 위의 부모만 갖고 있을 것 이기 때문에 노드의 개수만큼의 1차원 배열을 선언해둘 것이다.(자기 자신의 바로 위의 부모는 1세대 위라고 말하면 이해가 될까요? 나 - 부모님 관계...)
O(log n)의 방법에서는, 자신을 기준으로 1칸, 2칸, 4칸, 8칸... 떨어진 부모가 누구인지도 기록해둔다. (부모님이 누군지, 할아버지 할머니가 누군지 라고 생각합시다.)
그래서 한 칸씩 따라 올라가던 것을 껑충껑충 뛰어서 빠르게 LCA까지 도달하자!!라는 아이디어입니다.
3. LCA의 구현
위의 아이디어를 기반으로 알고리즘의 큰 틀을 생각해보자.
뭔가.. 껑충껑충 2의 승수로 뛰어간다는데,, 뭐가 필요할까?? 생각해보자.
parent배열을 선언해야 하는데.. 각 정점에 대해서 1, 2, 4, 8, 16...번째(2^0, 2^1, 2^2, ... , 2^k-1가 됨) 부모의 정보도 갖고 있어야 하니까 2차원 배열이겠구나.
→ parent[n][k] 여기서 n은 Tree에 있는 정점의 개수
k의 크기는 각 정점당 log(n)의 올림이 되겠구나.. (?????????????????라고 생각하실 것 같으니)
→Tree가 1줄로 나열되어 있다고 생각해 봅시다.
노드는 7개입니다. log_2(7)=2.xxx 이고, k=2라면, 배열은 [0, 1]의 범위를 가지기 때문에, 빠르게 탐색을 하다가 절반의 위치에서 멈춰야 합니다.
따라서, 올림 함수를 적용하여 k=3, 따라서 그림 5에서 parent배열의 크기는 [7(정점의 개수]][3]이 되고 k는 실제 [0,2] 범위를 가지고, 가장 끝에서 또 다른 끝까지 log2(n)의 속도로 탐색할 수 있게 되는 것입니다. (7을 1+2+4, 3번으로 탐색함)
첫 번째로 이러한 parent배열을 완성해야 합니다.
우선, Tree와 root는 주어졌다고 가정하겠습니다.
인접 리스트에 tree를 저장해 두고, root로 DFS를 실행하여 각 정점들을 한번 순회한다.
순회하면서 각 정점들과 연결된 부모들(바로 위의 노드)을 구하고, 깊이를 구한다.
깊이는 root를 0으로 하고, 한번 자식으로 내려가면 1, root의 자식의 자식은 2, 이런 방식으로 증가한다.
그림 1을 보시면 깊이가 1인 정점은 2개, 깊이가 4인 정점은 1개, 이렇게 됩니다.
/*
dfs(root)
*/
void dfs(int cur)
{
//정점 'cur'에 연결된 정점 next에 대하여,
for (int next : adj[cur]) {
if (depth[next] == -1) { //깊이가 갱신되지 않은 노드 라면(아직 방문 안 한)
parent[next][0] = cur; //next의 2^0번째 부모는 cur이다.
depth[next] = depth[cur] + 1; //next는 cur보다 깊이가 1더 깊다
dfs(next); // dfs 재귀 호출
}
}
return;
}
dfs함수.
main에서는 root를 기준으로 호출을 시작한다.
코드에 주석을 다 달아서 한 줄 한줄 어떤 동작을 하는지 다 적어 놓았습니다.
그래도 조금 말씀을 드리면,,
기본적인 dfs함수는 다 알고 있을 것이라고 생각하겠습니다.
탐색을 하면서, 모든 노드를 깊이 순서로 방문하게 될 텐데, 어떤 추가 동작을 해야 할까?라고 생각해보면,
자신의 바로 위 부모가 누구인지 알 수 있다.
깊이를 측정할 수 있다.
따라서, dfs를 하면서 위의 두 정보를 기록하도록 하자.
이제, 첫 번째 부모는 알게 되었다. 이제 껑충껑충 뛰기 위한 2, 4, 8,... 번째 부모를 찾아야 한다.
다음과 같은 아이디어를 통해 멀리 떨어져 있는 부모를 찾는다.
(1칸, 2칸은 몇 번째 부모 즉, 떨어진 거리,라고 생각하면 됩니다.)
나를 기준으로 2칸 떨어진 부모는,
나를 기준으로 1칸 떨어진 부모의 1칸 떨어진 부모다.
나를 기준으로 4칸 떨어진 부모는,
나를 기준으로 2칸 떨어진 부모의 2칸 떨어진 부모이다.
나를 기준으로 2^k칸 떨어진 부모는
나를 기준으로 2^(k-1)칸 떨어진 부모의 2^(k-1)칸 떨어진 부모이다.
라고 생각할 수 있다.
그래서, dfs함수를 통해 모두 1칸 떨어진 부모를 찾았으니까 이 정보를 가지고 2칸, 4칸, 8칸.. 한 칸씩 증가하면서 멀리 떨어진 부모들을 찾는다.
void connection()
{
// MAX는 log2(n)의 올림.
for (int k = 1; k < MAX; ++k) // 모든 k에 대하여,
for(int cur = 1; cur <=n; ++cur) // 모든 정점에 대하여,
parent[cur][k] = parent[parent[cur][k - 1]][k - 1];
//parent[cur][k] 2^k번째 부모는
//(first index) [parent[cur][k-1]] 나로 2^(k-1)번째 떨어진 부모의
//(second index) [k-1] 2^(k-1)번째,
// parent[parent[cur][k-1]][k-1] 부모이다.
return;
}멀리 떨어진 부모를 찾는 함수.
처음에 별다른 설명 없이 이 내용을 보면 배열의 인덱스 안에 또 배열이 있어서, 뭔가 막막한데.. 주석에 자세히 적어 놓았다.
위에 적어놓았던 아이디어를 단순하게 코드로 옮겨 적은 것이다. 이거는 정말 주석과 위의 아이디어를 보면 이해할 수 있을 거라 생각합니다.
이제 멀리 떨어진 부모까지의 정보를 다 구했다.
그러면... 어떻게 찾아가야 할까? 에 대한 궁금증이 생길 때가 되었다.
(아직 이해 안 해도 됨)
첫 번째로, 두 정점의 깊이를 같게 하자.
두 번째로, 부모가 같은 정점에 도달할 때까지 껑충껑충 뛰자.
이 두 가지로 찾는다.
정점 v, u 중 깊이가 더 깊은 것을 u, 그렇지 않은 것을 v로 하자,
u와 v의 깊이의 차는 3이다. dfs함수를 통해 depth 배열을 채워 놓았기 때문에
깊이의 차이는 depth[u]-depth[v]로 간단하게 구할 수 있다.
이제 정점 u를 정점 v의 깊이와 같아질 때까지 점프 점프할 것이다.
깊이의 차가 3... 우리는 점프를 2의 승수로 하니까.. 3을 2진수로 나타내어 보자. (이해를 위해)
11(2진수)이 된다. 즉, 1칸짜리 1번, 2칸짜리 1번 뛰면 된다.
예를들어, 깊이의 차가 11라고 해보자. 2진수로 나타내면 1011(2진수)이 된다. 이렇게 되면, 1칸 점프, 2칸 점프 하고 4칸은 그냥 패스하고 8칸 점프하면 된다.
이런 방식으로 점프할 것이다.
여기까지의 아이디어를 코드로 나타내면,
int LCA(int u, int v) {
//u를 더 깊은 정점으로 선택하자.
if (depth[u] < depth[v])
swap(u, v);
// 두 정점의 깊이 차이를 구하자
int diff = depth[u] - depth[v];
//깊이가 같아질 때 까지 (깊이의 차가 0일 때 까지)
for (int i = 0; diff != 0; ++i) {
// 2진수로 나타내었을 때, 1이라면 뛰어야 함. 1인지 체크
if (diff % 2 == 1)
u = parent[u][i]; //점프
// 오른쪽 shift와 같은 효과
diff /= 2;
}
}
위와 같다.
비트 연산을 많이 해본 적 없으면 이해하기가 힘들 수 있다. 그냥 단순이 이렇게 되는구나 라고 생각해도 되지만. 왜?라는 것에 대답을 하기 위해서는 위처럼 bitwise로 생각해 볼 필요가 있다.
자 이제 깊이가 같아졌다.
이제는 u와 v를 동시에 움직여 볼 거다.
이 Tree의 정점은 13개이다. 각 정점은 log2(13)의 올림인 4, 즉 16번째 위의 부모의 정보까지 갖고 있다. (부모가 없다면 그 값은 -1이다.)
16, 8, 4, 2, 1 이 순서대로 부모를 같이 볼 것이다.
16과 8은 tree를 벗어나기 때문에 생략하고(배열에서는 -1의 값을 가지고 있음),
그림 7에서 정점 u, v에서 4칸 떨어진 정점을 보자. root바로 밑의 정점으로 동일한 값을 나타냅니다.
그럼, 정점 u, v에서 2칸 떨어진 정점을 보자. LCA의 바로 밑의 정점이다.(문제를 보면 바로 딱 구할 수 있기 때문에.. 정답은 안다고 가정하겠습니다.)
두 정점이 다릅니다.
따라서, LCA는 아마도, 4번째이거나, 3번째가 될 수 있습니다. 여기서, 그림 7의 tree는 3번째가 LCA라 값이 같지만, 문제에 따라 다를 수도 있습니다.
여기서 '값'이란 정점 u, v의 x칸 떨어진 부모입니다.
여기서도 LCA를 아까 diff만큼 이동했을 때처럼 쫓아갈 수 있습니다.
단, 도착지를 LCA바로 밑의 자식이라고 생각해봅시다.
자, 정점 u, v에서 뛰었는데 부모가 동일하다?라고 하면 LCA바로 밑의 자식을 지나쳐 온 것이라고 생각합니다. (너무 멀리 뜀)
정점 u, v에서 뛰었는데 부모가 -1이다?(갱신 안 됨) 그러면 Tree의 범위를 벗어난 것이라 생각합니다.
이 두 가지 조건을 생각하여 diff때처럼 쫓아가게 되면 그림 7의 LCA바로 밑의 자식에게 도달하게 됩니다.
int LCA(int u, int v) {
//u를 더 깊은 정점으로 선택하자.
if (depth[u] < depth[v])
swap(u, v);
// 두 정점의 깊이 차이를 구하자
int diff = depth[u] - depth[v];
//깊이가 같아질 때 까지 (깊이의 차가 0일 때 까지)
for (int i = 0; diff != 0; ++i) {
// 2진수로 나타내었을 때, 1이라면 뛰어야 함. 1인지 체크
if (diff % 2 == 1)
u = parent[u][i]; //점프
// 오른쪽 shift와 같은 효과
diff /= 2;
}
// 두 정점이 다르다면,
if (u != v) {
//뛸 수 있는 최대한 먼거리 부터 뛰는데,
for(int i=MAX-1; i>=0; --i)
//-1이라면 Tree 바깥. (갱신 안되었기 때문)
//두 부모가 같다면 LCA가 아님. 그냥 공통 조상임.(마지막 1칸 점프때는 LCA이지만, 뛰지않음)
if (parent[u][i] != -1 && parent[u][i] != parent[v][i])
{
//LCA의 바로 밑 자식에게로 점프하는 중
u = parent[u][i];
v = parent[v][i];
}
//마지막 1칸.. 정점 u는 LCA가 됨.
u = parent[u][0];
}
//바로 찾았던 정점이 같았다면 LCA가 됨.
return u;
}
위의 두 가지 조건을 밑의 조건문에 넣읍시다.
반복문을 빠져나오면 LCA의 바로 밑 자식들에게 도달해 있고, 1칸 위의 부모(2^0)의 값을 사용해서 LCA를 구할 수 있습니다.
이렇게 LCA를 구할 수 있습니다.
밑의 문제는 정석적인 LCA문제로 위의 아이디어를 그대로 코드로 옮긴 내용입니다.
4. 문제 풀이
11437번: LCA
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
LCA 코드.
#include <cstdio>
#include <vector>
#include <string.h>
using namespace std;
const int MAX = 17; //ceil(log_2(n)))
int parent[50001][17]; //0~16
int depth[50001];
vector<vector<int>> adj; //adjacency list
int n, m;
void dfs(int cur)
{
for (int next : adj[cur]) {
if (depth[next] == -1) {
parent[next][0] = cur;
depth[next] = depth[cur] + 1;
dfs(next);
}
}
return;
}
void connection()
{
for (int k = 1; k < MAX; ++k)
for(int cur = 1; cur <=n; ++cur)
parent[cur][k] = parent[parent[cur][k - 1]][k - 1];
return;
}
int LCA(int u, int v) {
if (depth[u] < depth[v])
swap(u, v);
int diff = depth[u] - depth[v]; // diff가 100101011...
for (int i = 0; diff != 0; ++i) {
if (diff % 2 == 1)
u = parent[u][i];
diff /= 2;
}
if (u != v) {
for(int i=MAX-1; i>=0; --i)
if (parent[u][i] != -1 && parent[u][i] != parent[v][i])
{
u = parent[u][i];
v = parent[v][i];
}
u = parent[u][0];
}
return u;
}
int main()
{
scanf("%d", &n);
adj.resize(n + 1);
fill(depth, depth + n + 1, -1);
memset(parent,-1,sizeof(parent));
depth[1] = 0; //root
//make tree
for (int i = 0; i < n - 1; ++i){
int from, to;
scanf("%d %d", &from, &to);
adj[from].push_back(to);
adj[to].push_back(from);
}
dfs(1);
connection();
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
int u, v;
scanf("%d %d", &u, &v);
printf("%d\n", LCA(u, v));
}
return 0;
}
결과
지적, 댓글 환영입니다!
아,
m.blog.naver.com/kks227/220820773477
이 블로그에서 설명을 아주 잘 해주고 계십니다. :)
'알고리즘 > LCA' 카테고리의 다른 글
| boj, 백준) 13511. 트리와 쿼리2 ( C / C++) (0) | 2021.05.04 |
|---|---|
| boj, 백준) 3584. 가장 가까운 공통 조상 (C/C++) (0) | 2021.03.15 |
| boj, 백준) 11812. K진 트리 (C/C++) (0) | 2021.02.02 |