LCA(Lowest Common Ancestor) 알고리즘이란?
LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고,
두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다.
예를들어 다음과 같은 트리가 있다 생각해보자.
여기서 a,b의 공통 조상을 LCA(a,b)라고 하자.
LCA(14, 7)은 무엇일까?
위의 그림으로 우리는 LCA(14, 7) = 1임을 파악할 수 있다.
그렇다면 LCA(9,13)은 무엇일까?
예상했다시피 LCA(9,13) = 2임을 알 수 있다.
마지막으로 LCA(6,13) (혹은 LCA(13,6))은 무엇일까?
LCA(13,6) = 13, LCA(6,13) = 13임을 알 수 있다.
그림을 통해 LCA가 무엇인지 파악하였으니 이제 LCA(Lowest Common Ancestor) 알고리즘이 어떻게 돌아가는지 확인해야한다.
LCA(Lowest Common Ancestor) 알고리즘 동작 과정
우선 LCA 알고리즘을 해석하기 전에 이 블로그에서는 세그먼트 트리를 이용하지 않고 DP를 이용하여 해결함을 명시한다.
LCA 알고리즘의 시간 복잡도 :: O(lgN)
쿼리가 함께 존재할 경우 :: O(MlgN)
(아래 소스 코드분석 과정에서 lgN이 나오는 이유를 설명해두었습니다.)
첫번째로 입력받은 정점과 간선을 이용하여 양방향 그래프를 생성한다.
그 후 depth와 조상을 가지는 트리를 생성한다.
이때 조상은 2^0, 2^1, 2^2, ... 의 조상이 누구인지 알 수 있도록 한다.
depth와 2^k번째 조상을 가지고 있는 DP가 완성되었으면 이제 LCA(a,b) 즉, a와 b의 공통 조상이 누구인지 조사해야한다.
다음 그림을 보자.
LCA(6,8)의 값, 6과 8의 최소 공통 조상을 찾아야 한다.
이때 LCA 알고리즘에서는 다음과 같은 행동을 하도록 한다.
깊이가 더 깊은 노드를 깊이가 더 낮은 노드까지 노드를 올려준다.
이 말은 즉, 6(깊이 :: 6)이 현재 8(깊이 :: 3)보다 더 깊다.
따라서 6을 깊이 3까지 끌어올려주어야 한다.
이때 6이 가지고 있는 조상들을 이용하게 되는데, 6은 현재 다음과 같은 조상을 가지고 있게된다.
2^0번째 조상 :: 13
2^1번째 조상 :: 2
2^2번째 조상 :: 3
2^3번째 조상 :: 루트 노드를 넘어가버림(이때는 조상이 0이라고 가정한다.)
결국 6의 2^k번째 조상 중 가장 큰 조상부터 조사하여 8의 깊이보다 더 낮아지는 경우는 넘어가고,
그 외의 경우에는 6의 노드를 업데이트 해준다.
이 글은 말보다 그림으로 보는 것이 더 편하다.
6이 8과 깊이를 맞추기 위해 처음으로 2^2번째 조상을 확인하게 된다.
2^2번째 조상은 3이고 3의 깊이는 2이다. 따라서 8보다 더 낮은 깊이가 되었으므로 6의 2^2번째 조상으로 업데이트 하지 않는다.
이번엔 6의 2^1번째 조상인 2를 본다. 이것은 깊이가 4이고 8보다 깊이가 아직 더 깊으므로 6을 2로 업데이트 해준다.
이번엔 2의 2^0번째 조상인 12를 본다.
(처음 6의 2^k번째부터 보았다면 2^k, 2^k-1, 2^k-2...으로 관찰한다.
즉, 2의 2^2번째 조상이나 2^1번째 조상이 있더라도 이미 6에서 2^2번째, 2^1번째 조상을 확인하였으니
2에서는 2^0번째 조상만을 본다. 소스 코드에서 확인하는 것이 더 쉽다.)
12는 8과 깊이가 같으니 또 2를 12로 업데이트해준다.
이렇게 서로 다른 깊이를 가지는 노드를 같은 깊이를 가지는 노드로 만들어준다.
이 후로는 이제 LCA(a,b)에서 a와 b가 깊이가 같아졌으므로
서로 2^k만큼씩 조상을 올려다보며 조상이 같아질 때까지 노드를 타고 올라가면 된다.
만약 12와 8이 2^3만큼 조상을 올려다 본다면 둘다 0을 가리키고 있게된다.
따라서 이러한 상황은 무시하게 되고, 같은 노드를 가리키기 직전의 노드에서 멈추도록 하고
마지막에 그 서로다른 노드의 조상을 LCA로 지정함으로써 모든 알고리즘을 마친다.
즉, 12, 8은 3, 5노드에서 멈추게 되고 3의 1번째 조상( == 5의 1번째 조상 )인 1이 LCA가 된다.
LCA(Lowest Common Ancestor) 알고리즘 소스 코드
그림을 통해 대충 LCA 알고리즘을 훌터봤으니, 소스 코드를 통해 LCA(Lowest Common Ancestor)알고리즘을 알아보자.
소스 코드는 주석이 있는 코드와 주석이 없는 코드로 나누었다.
(같은 코드지만 주석이 매우 많아서 실제 코드를 보기 불편할 수 있기에 분리해 두겠습니다.)
아래 두개중 하나를 클릭하면 소스 코드를 볼 수 있습니다.
설명은 주석이 있는 코드를 기준으로 설명하려 한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | // DP(ac)배열 만드는 과정 void getTree(int here, int parent) { // here의 깊이는 부모노드깊이 + 1 depth[here] = depth[parent] + 1; // here의 1번째 조상은 부모노드 ac[here][0] = parent; // MAX_NODE에 log2를 씌어 내림을 해준다. max_level = (int)floor(log2(MAX_NODE)); for (int i = 1; i <= max_level; i++) { // tmp :: here의 2^(i-1)번째 조상 /* 즉, ac[here][i] = ac[tmp][i-1]은 here의 2^i번째 조상은 tmp의 2^(i-1)번째 조상의 2^(i-1)번째 조상과 같다는 의미 예를들어 i = 3일때 here의 8번째 조상은 tmp(here의 4번째 조상)의 4번째 조상과 같다. i = 4일때 here의 16번째 조상은 here의 8번째 조상(tmp)의 8번째와 같다. */ int tmp = ac[here][i - 1]; ac[here][i] = ac[tmp][i - 1]; } // dfs 알고리즘 int len = graph[here].size(); for (int i = 0; i < len; i++) { int there = graph[here][i]; if (there != parent) getTree(there, here); } } |
이 코드에서 max_level의 의미는 문제에서 주어지는 최대 노드수에
log2를 취해 2^k번째 조상을 최대 몇번 갈 수 있는지 생각한 방식이다.
만약 노드 수의 최대가 100000이라면 2^16 = 65,536 이므로 max_level은 16임을 알 수 있다.
즉 아무리 최악의 경우라도 가장 아래의 노드가 2^16을 통해 루트 노드를 향해 갈 수 있지,
2^17을 해버리면 루트 노드를 넘어가버린다.
DP를 만들기 위한 점화식을 살펴보면 다음과 같다.
ac[here][i] = ac[ac[here][i - 1]][i-1];
이것을 보기 좀 더 편하게 해서
tmp = ac[here][i-1];
ac[here][i] = ac[tmp][i-1];이라고 설정한다.
이 점화식의 의미는 위의 주석에 매우 자세히 설명되어있다.
// tmp :: here의 2^(i-1)번째 조상
/*
즉, ac[here][i] = ac[tmp][i-1]은
here의 2^i번째 조상은 tmp의 2^(i-1)번째 조상의 2^(i-1)번째 조상과 같다는 의미
예를들어 i = 3일때
here의 8번째 조상은 tmp(here의 4번째 조상)의 4번째 조상과 같다.
i = 4일때 here의 16번째 조상은 here의 8번째 조상(tmp)의 8번째와 같다.
*/
1 2 3 4 5 6 7 8 | // dfs 알고리즘 int len = graph[here].size(); for (int i = 0; i < len; i++) { int there = graph[here][i]; if (there != parent) getTree(there, here); } |
그리고 위의 알고리즘을 통해 양방향 그래프에서 단방향 그래프 즉, 트리로 생성하기 위해
if(there != parent)라는 요소를 추가하여 getTree(there, here);로 트리 및 깊이, 조상을 기록할 수 있게 한다.
만약 there == parent인곳도 dfs로 들어간다면 영원히 빠져나올 수 없는 재귀가 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | if (depth[a] != depth[b]) { // depth[b] >= depth[a]가 되도록 swap if (depth[a] > depth[b]) swap(a, b); // b를 올려서 depth를 맞춰준다. /* 이렇게하면 만약 max_level이 4라면 2^4 -> 2^3 -> 2^2 -> 2^1 -> 2^0방식으로 찾아갈텐데 결국 1, 2, 3, 4, 5 ..., 31까지 모두 찾는 방식과 같아진다. 예를들어, i가 4일때와 1일때 만족했다 치면 depth[a] <= depth[ac[b][4]]에 의해 b = ac[b][4];가 되어 b는 b의 16번째 조상을 보고 있을 것이고 depth[a] <= depth[ac[b][1]]에 의해(현재 b는 처음 b의 16번째 조상인 b로 바뀌었다.) b = ac[b][1];이 되어 b는 b의 2번째 조상을 보게 된다. 즉, b의 16번째 조상의 2번째 조상을 보는 것이니 b의 18번째 조상을 보게 된다. (하고자 하는 말은 3번째, 7번째, 11번째 이런 조상들도 모두 볼 수 있다는 의미이다.) */ for (int i = max_level; i >= 0; i--) { // b의 2^i번째 조상이 a의 depth보다 크거나 같으면 계속 조상을 타고간다. if (depth[a] <= depth[ac[b][i]]) b = ac[b][i]; } } |
이 코드는 a와 b의 깊이를 같도록 해주는 코드이다.
여기서 의문점이 드는 상황이 2^k번째가 아닌 홀수번째들은 어떻게 파악하냐인데
for문을 잘 보면 max_level부터 시작하기 때문에(이로인해 O(lgN)이 가능하다.)
모든 조상에 대해 파악이 가능하고, depth를 맞출 수 있다.
그러한 내용은 주석을 통해 매우 자세히 설명해두었다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | int lca = a; // a와 b가 다르다면 현재 깊이가 같으니 // 깊이를 계속 올려 서로 다른 노드의 조상이 같아질 때까지 반복한다. // 즉, 서로 다른 노드(2,3)의 조상이 1로 같다면 lca = ac[2][0]에 의해 2의 조상이 1임을 알 수 있고 // 마찬가지로 ac[3][0] 또한 3의 조상이 1임을 알게되며 알고리즘이 끝이난다. if (a != b) { for (int i = max_level; i >= 0; i--) { if (ac[a][i] != ac[b][i]) { a = ac[a][i]; b = ac[b][i]; } lca = ac[a][i]; } } |
이제 이 코드에 접어드는 순간 a와 b는 depth가 같아진 서로 다른 노드이다.
현재 lca는 a라고 가정을 해 두고 만약 a == b라면 아래와 같은 상황에서 나타난 lca이기에 그대로 lca는 a가 된다.
그 외의 경우에는 이제 깊이는 같고 노드가 서로 다르니 공통 조상을 찾으러 간다.
이때도 max_level부터 시작하기 때문에 모든 노드에 대해 조사가 가능하고, (이로인해 O(lgN)이 가능하다.)
결국 서로 같은 조상이 나오기 직전까지 반복 한 후
lca = ac[a][i]에 의해 서로 조상이 같은 다른 노드 a, b둘중 하나의 노드의 조상이 lca가 됨을 알 수 있다.
(서브 트리의 노드 어디에서도 못만나도 결국 루트노드에서 만나게 되어있다.)
'Applied > 알고리즘' 카테고리의 다른 글
| 최소 스패닝 트리(Minimum Spanning Tree, MST) (23) | 2017.04.05 |
|---|---|
| 위상 정렬(Topological Sort) (0) | 2017.03.31 |
| 이진 탐색 트리 특징을 이용한 빠른 삽입, 탐색 (2) | 2017.03.06 |
| 전위, 중위 순회를 알 때 후위 순회 구하는 알고리즘 (0) | 2017.03.03 |
| LCP 알고리즘(Longest Common Prefix) (4) | 2017.02.25 |