[백준] No.11438 - LCA 2 (C++, 최소 공통 조상)

문제

https://www.acmicpc.net/problem/11438

11438번: LCA 2

 

 

풀이

 

solved.ac 난이도: Platium 5

 

이전 단계 문제인 LCA 와는 다르게  입력의 크기가 크고 제한 시간이 더 짧다.

따라서 최소 공통 조상 알고리즘을 최적화해야 한다.

 

최적화는 다이나믹 프로그래밍을 이용한 전처리를 통해 LCA를 찾는 시간 복잡도를 O(log Tree_heigth)으로 줄일 수 있다.

 

이를 위해 x의 2^k(2의 k승)번째 조상을 parent[x][k]라고 하자.

k=0 이라면, 2^0 = 1으로 x의 부모 노드이다. parent[x][1] 

k=1 이라면, 2^1 = 2으로 x의 두번째 조상, 즉 부모 노드의 부모로 아래와 같이 나타낼 수 있다.

parent[x][1] = parent[parent[x][0]][0]

 

k=2, x의 4번째 조상으로 x의 두 번째 조상(parent[x][1])의 두 번째 조상이다.

parent[x][2] = parent[parent[x][1]][1]

.

.

.

따라서 2^k번째 조상은  

parent[x][k] = parent[parent[x][k-1]][k-1]로 나타낼 수 있다.

 

예를 들어 아래의 트리에서 5번 노드의 4번째 조상을 구해보자.

 

parent[5][0] = 4, parent[4][0]=3, parent[3][0] =  2, parent[2][0]=1,

parent[5][1] = parent[ parent[5][0] ][0] = parent[4][0]=3,

5번 노드의 2^1번째 조상은 5번 노드의 2^0번째 조상(4번 노드)의 2^0번째 조상이다.

 

parent[5][2] = parent[ parent[5][1] ][1] = parent[3][1] = parent[ parent[3][0] ][0] = parent[2][0] = 1

 

 

 

이와 같은 계산은 x의  2^k번째 조상을 구하기 위해 x의  2^(k-1)번째 조상의 값을 참조하기 때문에 bottom-up방식으로 k=0부터 한 단계씩 구해나가면 트리의 높이를 k라 할 때 O(k logN)의 복잡도로 모두 구해낼 수 있다.

 

이처럼 x의 2의 제곱 수들의 조상을 미리 구해 놓는다면 x의 13(이진수로 1101)번째 조상은

x의 첫 번째(2^0) 조상에서 두번째(2^1) 조상, 그리고 다시 그 첫번째(2^0) 조상으로 이동하면 구해낼 수 있다.

(0001) -> (0100) -> (1000)

parent[x][13] = parent[ parent[ parent[x][0] ][1] ][0]

 

즉, 노드의 개수 N의 2진수 표현 시 사용되는 비트수 logN 만큼의 시간 복잡도로도 k번째 조상을 구해낼 수 있다.

 

이를 구현하기 위해 2의 제곱수의 조상을 저장하는 배열 parent[x][k]을 사용하자.

 

문제에는 연결된 정점의 보모 자식 관계가 주어지지 않으므로 아래의 함수를 루트 노드에서부터 호출하여 깊이와 부모를 결정하자.

 

void FindParentDFS(int par, int now, int dep){
  if(adjection[now].size() ==0)
    return;
  
  parent[now][0] = par;   //2^0 = 1, 1칸 위의 조상, 즉 부모 노드
  depth[now] = dep;
 
  for(int i=0; i<adjection[now].size() ; ++i){
    if(adjection[now][i] != par)
      FindParentDFS(now, adjection[now][i],dep+1);
  }
}
 

 

 

 

이후 parent의 전처리 과정을 진행하자.

 

for(int k = 1 ; k<=max_height ; ++k)
  for(int idx=2; idx<=node_num ; ++idx)
    if(parent[idx][k-1] != 0)
      parent[idx][k] = parent[parent[idx][k-1]][k-1];

 

parent[idx][k-1] == 0(2^(k-1)번째 조상이 루트 노드를 넘어간 경우 ) 이라면

parent[idx][k] 또한 0일 수밖에 없으므로 패스해주자.

 

 

전처리 과정이 끝났다면 a와 b번 노드의 LCA를 구하는 함수를 작성하자.

a와 b의 깊이가 서로 다르다면 더 깊은 노드를 일단 같은 높이로 올려주어야 서로 같은 거리만큼 떨어진 LCA를 구할 수 있다.

 

이를 위해서 두 깊이의 차이(dif)만큼 더 깊은 노드의 dif번째 조상을 구해주자.

이때 단순히 dif 번 조상으로 올라가는 경우, 최악의 경우 치우 처진 트리의 리프 노드에서 루트 노드까지 올라가야 할 수 있다.

따라서 parent배열을 이용하자.

만약 dif =13이라면, 위의 예시처럼

parent[x][13] = parent[ parent[ parent[x][0] ][1] ][0] 로 한 단계씩 올려가며 계산해주자.

 

서로 같은 높이를 만들었다면 LCA를 구할 차례이다.

앞에서 처럼 특정 순서의 조상을 구하는 것은 몇번째 조상인지를 이미 알고 있기 때문에 쉽게 계산이 되지만 우리는 a와 b의 몇번째 조상이 LCA인지 알 수 없다.

따라서 parent[a][트리의 높이(k)]에서 k를 1씩 줄여가며 탐색을 하자.

 

만약 parent[a][k] == parent[b][k] 이지만, parent[a][k-1] != parent[b][k-1] 이라면

LCA는 2^(k-1)번째 조상에서 ~ 2^k 번째 조상의 사이에 존재한다. (LCA 이후의 조상들도 모두 공통될 수 밖에 없기 때문)

이런 경우 a와 b를 각각 parent[a][k-1]과 parent[b][k-1]로 업데이트 하여 k가 줄어들 때마다

2^(k-1)번째 조상과 2^k 번째 조상의 간격을 줄여준다.

 

 

int FindLCA(int a, int b){
 
  if(depth[a] != depth[b]){ //depth[a] = depth[b]이도록 맞춰줌.
    if(depth[a] < depth[b]) //depth[a] != depth[b]라면 항상 a가 더 깊게
      swap(a, b);
 
    int dif = depth[a] - depth[b];
 
    for(int i =0; dif>0 ; ++i){
      if(dif%2 ==1) 
        a = parent[a][i];
      dif = dif>>1;
    }
  } 
 
  if(a != b){
    for( int k = max_height; k>=0 ; --k )
      if(parent[a][k] != 0 && parent[a][k] != parent[b][k]){
        a = parent[a][k];
        b = parent[b][k];
      }
 
    a=parent[a][0];
  }
 
  return a;
}

 

예를 들어 13(01101)번째 조상이 LCA라고 하자.

 

k=4인 경우 , parent[a][4] == parent[b][4] 일 것이다.

 

k=3인 경우, parent[a][3] != parent[b][3] 이다.

따라서 a=  parent[a][3], b =  parent[b][3]로 변경한다.

이제 LCA는 2^4과 2^3사이의 구간 (8, 16] = (9~16)에 존재한다.

 

변경된 a와 b에서 k=3인 경우는 더 이상 LCA가 존재 가능한 구간 사이에 포함되지 않는다.

=> parent[a][3] == parent[b][3] 

 

또한 a의 8번째 조상으로 이동 했으므로 13번째 조상으로 이동하기위해서는 5(= 13 - 8)번째 조상으로 이동해야 한다.
(1101 - 1000) = 101

 

k=2인 경우, parent[a][2] != parent[b][2] 이다.

동일하게 a=  parent[a][2], b =  parent[b][2]로 변경하면 이제 최종적으로

(101 - 100) = 1, 첫 번째 조상으로 이동 시키면 된다.

 

k=1인 경우, 2^1 = 2로 두번째 조상이다. parent[a][1] == parent[b][1]

 

k=0인 경우, LCA이기 때문에  parent[a][0] == parent[b][0]이다.

parent[a][0] != parent[b][0]이 아니기 때문에 최종적으로 a = parent[a][0]를 추가적으로 진행해주자.

 

이처럼 k를 트리의 높이에서 1씩 줄여가는 연산으로 LCA를 O(logN)의 복잡도로 찾을 수 있다.

 

 

이번에 소개한 다이나믹 프로그래밍을 이용한 LCA의 구현 이외에서 구간 트리(세그먼트 트리)를 이용한 구현도 존재한다.

알고스팟 - 족보 탐험(FAMILYTREE)★+ 세그먼트 트리로 구현 - 상

 

 

코드