LCA란, 트리상에서 어떤 두 정점 u, v가 있을 때, u이거나 u의 조상이면서 동시에 v이거나 v의 조상인 노드들 중 가장 깊은 노드입니다.
트리의 특성상 싸이클이 없으므로, 두 정점 u와 v의 LCA를 w라 했을 때 u-w-v는 두 정점의 최단 경로라고도 할 수 있겠죠 :)
LCA를 찾는 방법은 여러가지가 있는데, 세그먼트 트리를 사용하는 방법도 있지만, 저는 각 정점의 모든 정보들(깊이, 부모 정보, 부모의 부모 정보 등..)을 미리 저장해두고 LCA문제를 해결해보았습니다. 이렇게 하면 O(logN)만에 LCA를 찾을 수 있습니다.
LCA를 가장 단순하고 쉽게 찾는 방법을 생각해보면,
- 모든 간선 정보를 저장한다.
- 각 정점의 깊이를 파악한다. (-> 완전 탐색 사용)
- 더 깊이가 깊은 정점에서 깊이가 같아질 때까지 부모 정점으로 이동한다.
- 정점의 깊이가 같아졌으면 두 정점이 동시에 부모 정점으로 이동한다.
- 같은 정점에 도달하면 그것이 LCA이다.
그러나 그래프가 한쪽으로 치우친 극단적인 경우에는 시간복잡도가 O(logN)이 나오게 됩니다.
그렇다면 '부모의 모든 정보를 기입한다.' 는것 무슨 의미일까요?
기존 LCA문제 해결방식은 parent 1차원 배열을 두고 부모 정보를 기입했지만, 2차원 배열 parent[V(정점의개수)][log2V] 을 만듭니다.
parent[u][k]는 정점 u의 2^k번째 부모를 말합니다. 이 배열을 이용하게 되면, 정점을 건너뛰는 것을 좀 더 빨리 할 수 있습니다.
2^(k+1) = 2^k + 2^k이므로, 이를 배열에 해당하면 parent[u][k+1] = parent[ parent[u][k] ][k]의 식으로 구할 수 있습니다.
따라서, k=i(i는 임의의 수)일 때의 정보가 주어진다면, k=i+1일 때의 정보를 구할 수 있는 것입니다.
* 추가 설명) parent[u][k+1] = parent[ parent[u][k] ][k]
좌변은 정점 u의 2^(k+1)번째 부모를 말합니다. 2^k에서 k가 각각 0, 1, 2 가 주어지면 그 값은 1, 2, 4, .. 과 같이 주어진다는 것은 이해가 되시죠? 위의 식을 이해하기 위해 차근차근 되짚어 봅시다. 우선, 왜 1, 2, 4 의 부모를 찾게 되는 것일까요?
만약, 두 정점의 깊이 차이가 11이 난다고 해봅시다. 이것은 누가 보기에도 차이가 많이 남을 알 수 있습니다. 그런데 한 정점씩 올라가게 되면 시간이 O(N)이 걸리게 되니 2의 제곱씩 올라가자고 하는 것입니다. 2의 제곱만큼 올라가자는 건 깊이 차이를 2의 제곱만큼 줄이자는 것이죠. 다시 말하면, 11 차이가 났으니 내 위로 첫 번째 부모(2^0번째), 내 위로 두 번째 부모(2^1의 부모), 내 위로 네 번째 부모(2^2)의 위치로 이동하는 것이죠.
다시 위 식을 돌아보면, parent[u][k]는 현재 u 정점에서 2^k번째 부모임을 뜻합니다. 이 부모를 A라고 칭합시다. 그 다음 이 부모 A의 2^k번째 부모가 바로 parent[u][k+1]임을 말합니다. 현재 u정점에서 2^(k+1) 번째 부모는 결국 2^k의 부모의 2^k부모를 말합니다 조사 '의' 때문에 수식 2^k + 2^k 보다는 2^k * 2^k등 다양한 수식으로 오해하실 수 있지만, 트리 구조를 생각해보면 2^k의 단계만큼 올라간다고 생각하면 쉽게 2^k + 2^k로 생각하실 수 있으실겁니다. :)
이제 이 parent배열을 사용해서 LCA를 빨리 찾아봅시다.
★주요 논리★
두 정점 u, v가 있고 depth[u]>=depth[v]일 때,
- depth[u] > depth[v]일 때, u와 parent[u]로 대체하는 것을 반복합니다.
- u != v 일 때, u를 parent[u], v를 parent[v]로 동시에 대체하는 것을 반복합니다.
[1 구현]
for(int j = 0; diff != 0; j++){
if( diff%2 != 0){
num1 = parent[num1-1][j]+1;
}
diff /= 2;
}
둘의 깊이차이가 diff, 정점 u는 num1입니다. 정점 num1에 부모 정점을 대입함으로써 부모로 이동하는 것입니다. 'num-1'을 이유는 index 값이 '실제 정점 값 - 1'로 이루어졌기 때문입니다
다시 이해를 위해 diff = 11 이라고 가정해보겠습니다. 부모로 이동하는 과정가운데 이동한 depth의 합산을 step으로 보여드리겠습니다.
- j = 0 일 때, num1의 첫 번째 부모로 이동 => step += 1
- j = 1 일 때, 첫 번째 부모의 2^1 로 이동 => step += 2
- j = 2 일 때, 두 번째 부모의 2^2로 이동 => step += 4 ...(이후생략)
이런식으로 step은 2의 제곱씩 합산되어질 것입니다. 이동한 값이 깊이 차이보다는 작아야 하기 때문에 diff >= step 을 만족해야 합니다. 여기서 왜 홀수일 때만 num1 = parent[num-1][j] + 1 을 수행해주느냐?
예를 들어)
- diff 가 4인 경우 diff : 4 -> 2 -> 1 / j: 0 -> 1-> 2 가 되죠. 그리고 마지막 diff가 1인 경우 2^2으로 이동하죠.
- diff가 6인 경우는 diff: 6 -> 3 -> 1 / j: 0 -> 1 -> 2 가 됩니다. 그리고 2^1 +2^2으로 이동합니다.
- 그렇다면, diff 가 5인 경우 diff: 5 -> 2 -> 1, j: 0 -> 1 -> 2 가 됩니다. 2^0 + 2^2 이 됩니다.
이제 어느 정도 눈치 채셨나요? 이는 이진수 기법을 나타낸 것인데요, 10진수를 2진수로 바꾸는 방법을 생각해보면 쉽습니다. 2진수로 바꿀 때,나머지를 역순으로 기입하여 2진수를 완성하죠. 즉 위의 for문은 diff라는 10진수를 2진수로 바꾸는 과정입니다. 나머지가 0이 되는 부분은 더하지 않고, 나머지가 1이 되는 부분만 더하면 diff가 2진수가 완성됩니다.
또한, for문은 항상 diff /= 2 를 수행합니다. 이는 2진수로 바꾸는 과정 수행 중을 의미합니다. diff != 0 조건 아래, 10진수를 2진수로 바꾸기 위해서 원래 숫자를 계속해서 2로 나누는 과정은 step <= diff 을 만족하는 것이 당연합니다.
[2 구현]
2의 경우 이제는 depth[u] 와 depth[v]가 같아졌습니다! 둘의 깊이는 항상 똑같이 유지되면서 정점들이 바뀌어갈 겁니다. parent[u][k] != parent[v][k]은 정점 u의 2^k 번째 부모와 정점 v의 2^k 번째 부모가 같지 않다는 것입니다. 둘의 깊이가 같은 조건 아래, 이는 두 정점 u, v의 LCA의 깊이는 둘로부터 2^k보다는 멀리 떨어져 있음이 확실합니다. 그런데 만약 parent[u][k+1] == parent[v][k+1]이면 2^k < LCA < 2^(k+1) 를 만족합니다.
이제 k를 큰 값부터 시도하면서 순회하여, parent[u][k] != parent[v][k]이면 u, v 를 동시에 2^k만큼 위로 올려보내면 됩니다.
if(num1 != num2){
for(int j=(int)MAX-1; j>=0; j--){
if((parent[num1-1][j] != -1) && (parent[num1-1][j] != parent[num2-1][j])){
num1 = parent[num1-1][j]+1;
num2 = parent[num2-1][j]+1;
}
}
num1 = parent[num1-1][0]+1;
}- for문 안의 if 조건문으로 k가 큰 값부터 2^(k+2), 2^(k+1), 2^k 순으로 검사합니다. 만약 j=k일 때, 같지 않다면 위의 설명처럼 해당 2^k보다는 멀리 떨어져 있다는 것입니다. 따라서 num1(=u)과 num2(=v)를 업데이트 합니다.
- 줄어든 j로 다시한번 for 문을 진입합니다. 만약 같게된다면 if문을 수행하지 않습니다.
- for문을 끝내고 나면, num1 = parent[num1-1][0]으로 한 번 더 올려줍니다.
- num1은 LCA 가 됩니다.
* 추가 설명)
예를 들어, u와 v의 최소 공통 조상의 깊이 차이가 '1' 이었다고 해봅시다. 그렇다면 한 번도 num1, num2가 없데이트 되지 않고, j = 0 인 상황까지 오게 될 것입니다. 이 또한 parent[num1-1][0] == parent[num2-1][0]에 해당되어 for 문을 나오게 될 것이고 num1 = parent[num1-1][0] 이 되는 것이 이해가 될 것입니다.
자 그럼, 만약 j = 3일 때 parent[num1-1][3] == parent[num2-1][3]이 일치 했다는 것은 j 가 3보다 큰 수에 대해서는 모두 일치가 되었다는 것을 뜻합니다. 트리의 구조를 생각해보았을 때, 2^3의 부모가 일치한다는건 그보다 더 높이 위치한 2^4 부모가 일치한다는 것입니다. 여기서 2^3까지는 동일하나 2^2, 2^1, 2^0과는 부모가 동일하지 않은 경우, 계속해서 깊이가 +2^2, +2^1, +2^0 인 정점으로 업데이트 됩니다.
그래프의 정점은 공통 조상을 향해 올라갑니다. 부모가 같으면 업데이트를 하지 않습니다. j=0일 때 조상이 같은 경우와 같지 않은 경우를 생각해보겠습니다. 조상이 같은 경우는 첫 번째 문단과 같습니다. 조상이 같지 않은 경우는 두 번째 단락처럼 계속해서 업데이트로 정점이 올라가게 되죠. 즉 깊이 차이가 1인 지점까지 오게 되는 것입니다. 그렇기 때문에 num1 = parent[num1-1][0] 을 수행하는 것이죠
전체 코드
import java.util.Scanner;
import java.util.ArrayList;
public class Ancestor {
static int V;
static int [] depth;
static int [][] parent;
static boolean [] visit;
static double MAX;
static int count =0;
static ArrayList<Integer> [] arrli;
public static void main(String args[]){
Scanner scan = new Scanner(System.in);
int N = scan.nextInt();
for(int k=0; k<N; k++) {
count = 0;
V = scan.nextInt(); //노드 갯수
int E = scan.nextInt(); // 간선 갯수
int one = scan.nextInt();
int two = scan.nextInt();
depth = new int[V];
MAX = Math.log10(V) / Math.log10(2);
parent = new int[V][(int)MAX];
visit = new boolean[V];
arrli= new ArrayList [V];
for (int i = 0; i < V; i++) {
for (int j = 0; j < (int) MAX; j++) {
parent[i][j] = -1;
}
}
for (int i = 0; i < V; i++) {
arrli[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
//실제 값 -1 로 인덱스 값 설정
int par = scan.nextInt();
int chi = scan.nextInt();
arrli[par-1].add(chi-1);
}
// 각 노드의 depth , parent[v][0]저장,
DFS(0);
//parent 배열 채움
for (int j = 0; j < (int) MAX - 1; j++) {
for (int i = 1; i < V; i++) {
if (parent[i][j] != -1) {
parent[i][j + 1] = parent[parent[i][j]][j];
}
}
}
int ans = findAncestor(one, two);
int count = findAnswer(ans);
System.out.println("#"+(k+1)+" "+ans+" "+count);
}
}
public static int findAnswer(int ans){
int num = ans-1;
visit[num]=true;
count+=1;
for(int j=0; j<arrli[num].size(); j++){
int n = arrli[num].get(j);
if(!visit[n]){
findAnswer(n+1);
}
}
return count;
}
public static int findAncestor(int num1, int num2){
int oneDep = depth[num1-1];
int twoDep = depth[num2-1];
int diff=0;
if(oneDep < twoDep){
//num1 > num2
int temp = num2;
num2 = num1;
num1 = temp;
}
diff = Math.abs(twoDep-oneDep);
//깊이 차를 없애며 이동
for(int j=0; diff!=0; j++){
if(diff%2 != 0){
num1 = parent[num1-1][j]+1;
}
diff = diff/2;
}
if(num1 != num2){
for(int j=(int)MAX-1; j>=0; j--){
if((parent[num1-1][j] != -1) && (parent[num1-1][j] != parent[num2-1][j])){
num1 = parent[num1-1][j]+1;
num2 = parent[num2-1][j]+1;
}
}
num1 = parent[num1-1][0]+1;
}
return num1;
}
public static void DFS(int num){
for(int i=0; i<arrli[num].size(); i++){
int next = arrli[num].get(i);
if(depth[next]==0){
parent[next][0]=num;
depth[next]=depth[num]+1;
DFS(next);
}
}
}
}
'알고리즘 공부' 카테고리의 다른 글
| BFS 공부 (0) | 2019.03.20 |
|---|---|
| DFS(깊이 우선 탐색) 알고리즘 (0) | 2019.03.07 |
| 그리디 알고리즘 (0) | 2019.03.06 |
| 동적계획법 - 다익스트라 알고리즘 (0) | 2019.03.06 |