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

문제

 

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

11437번: LCA

 

 

풀이

 

solved.ac 난이도: Gold 3

 

트리에 속한 두 노드의 최소 공통 조상(Lowest Common Ancestor)을 찾는 문제이다.

동일한 문제이지만 입력의 수가 더 많고 시간제한이 짧은 LCA 2와는 다르게 단순히 구현해도 시간안에 해결할 수 있다.

 

일단 LCA2를 푸는 기초가 되는 풀이를 살펴보자.

두 노드는 어느 곳에 위치하든 조상 노드로 한 칸씩 위로 올라가다 보면 서로 공통된 조상을 찾을 수 있다.

이때 최소 공통 조상의 위치는 공통 조상 중 가장 트리에서의 높이(heigt)가 높은(루트의 높이를 0이라 할 때) 노드라 할 수 있다.

따라서 a와 b노드의 LCA를 찾고 싶다면 일단 두 노드의 높이를 갖도록 맞추어 준다.

만일 a가 더 높이가 높다면 조상 노드로 한칸씩 이동하며 b노드의 높이와 맞추어준다.

 

높이를 맞추었다면 두 노드를 조상 노드로 한 단계씩 높여가며, 동일한 조상 노드가 발견된다면 해당 노드가 LCA가 된다.

 

 

Node* FindLCA(Node* a, Node* b){
  Node* p1 = a;  
  Node* p2 = b;
 
  if(a->height != b->height){   //높이가 다르면 같아지게 만듬
    if(a->height < b->height){  //p1은 더 높이가 큰 경우
      p1 = b;
      p2 = a;
    }
 
    while(p1->height != p2->height)
      p1 = p1->parent;
  } 
 
  while(p1 != p2){
    p1 = p1->parent;
    p2 = p2->parent;
  }
 
  return p1;
}

 

해당 알고리즘은 한 단계씩 조상 노드로 이동하므로 LCA가 p1의 k번째 조상이라면 O(k)의 시간 복잡도를 갖는다.

따라서 LCA 2와 같이 입력이 크고 시간 제한이 있는 문제에서는 시간 초과가 발생할 수 있다.

 

코드