[알고스팟] FAMILYTREE - 족보 탐험 (C++, LCA, 세그먼트 트리)

문제

 

https://algospot.com/judge/problem/read/FAMILYTREE

algospot.com :: FAMILYTREE

 

 

풀이

 

종만북 난이도: 상

 

최소 공통 조상(Lowest Common Ancestor, LCA)를 세그먼트 트리로 풀어보는 문제이다.

LCA의 구현에는 단순한 구현과 최적화를 거친 구현이 존재한다.

단순 구현: 백준 - LCA(11437) - Gold 3

최적화 구현: 백준 - LCA 2(11438)★ - Platium 5

 

하지만 이번에는 세그먼트 트리를 이용하여 LCA를 구현해보자.

구현의 핵심이 되는 아이디어는 트리를 전위 순회(preorder)한 순서(재귀 호출이 끝난  노드로 돌아오는 것도 포함)를 이용하는 것이다. 즉, 노드를 지나는 모든 순간마다 방문 순서 배열에 추가해준다.

 

 방문 순서 배열의 크기

모든 노드의 개수를 n개라할 때 트리 구조는 사이클이 존재하지 않기 때문에 n-1개의 경로가 존재한다.

DFS로 모든 노드를 전위 순회할 때 각 경로는 하위로 내려갈 때 한번, 올라갈 때 한 번으로 총 두 번씩 사용된다.

따라서 방문 순서 배열의 크기는 2(n-1) + 1(루트에서 시작하는 것을 포함) = 2n - 1 이 된다.

 

그렇다면 순서 배열을 LCA를 찾는데에 어떻게 이용해야할까?

아래와 같은 트리 구조를 생각해보자.

해당 트리에서 부모 노드는 자식 노드보다는 작은 번호를 갖는다.(이는 자식 노드보다 부모 노드를 먼저 방문하는 DFS나 BFS방식으로 간단히 구현 가능)

 

 

이 트리의 순서 배열은 다음과 같다.

1, 2, 3, 2, 4, 5, 4, 2, 1, 6, 7, 8, 7, 1

 

여기서 2의 서브 트리와 7의 서브 트리를 표시해보자.

1, 2, 3, 2, 4, 5, 4, 2, 1, 6, 7, 8, 7, 1

 

만약 2의 서브 트리에서의 특정 노드 u 와 7의 서브트리에서의 노드 v의 LCA를 찾고 싶다면(LCA는 항상 1이다.)

해당 노드들이 처음 등장하는 위치를 구간으로 만든다.

 

예를 들어 5와 8의 LCA를 구하는 경우,

5가 처음 등장하는 위치는 6번째이고, 7이 처음 등장하는 위치는 11번째이다.

 

이 두 위치를 구간으로 설정하고 해당 구간에서의 최솟값(작을수록 상위 노드 이므로)이 u, v의 LCA가 된다.

1, 2, 3, 2, 4, 5, 4, 2, 1, 6, 7, 8, 7, 1

 

이는 LCA의 자식 노드들이 루트 노드로 구성되는 서브 트리들에서 항상 성립된다.

왜냐하면 u를 포함하는 서브 트리에서 v를 포함하는 서브 트리로 넘어가려면  LCA를 항상 거쳐야 하기 때문이다.

LCA보다 작은 값은 LCA의 서브 트리를 모두 순회하기 전에 등장할 수없기 때문에 질의 구간에 포함될 수 없다.

 

LCA를 구했다면 이제 촌수(LCA로부터의 거리)를 구해야 한다.

이는 모든 노드의 트리에서의 깊이(depth)를 저장하여 u와 LCA의 거리(depth[u] - depth[lca]) + v와 LCA의 거리(depth[v] - depth[lca]) = depth[u] + depth[v]+2*depth[lca]로 구할 수 있다.

 

 

문제에서는 노드의 번호가 부모가 더 작도로 주어지지 않으므로 DFS방식으로 자식 노드를 방문하여 일련번호(Serial Number)를 새로 붙여주자.

각 노드가 처음 방문되는 위치는, 모든 노드는 DFS방식으로 방문 시 한 번씩만 방문되기 때문에

방문 시, 순서 배열의 크기가 처음 방문되는 위치이다.

 

이를 구현한 함수가 void Traverse(int here, int d )이다.

vector<int> trip에는 방문 순서를

no2serial[] 에는 노드 번호에 대응하는 일련번호를 ,

serial2no[]에는 일련번호에 대응하는 노드 번호를

depth[]에는 해당 노드의 깊이를

locInTrip[]에는 해당 노드가 첫 방문된 trip에서의 위치를 저장한다.

 

void Traverse(int here, int d ){
  no2serial[here] = nextSerial;
  serial2no[nextSerial] = here;
  ++nextSerial;
  depth[here] = d;
 
  locInTrip[here] = trip.size();
  trip.push_back(no2serial[here]);
 
  for(int i=0; i<child[here].size() ; ++i){
    Traverse(child[here][i] , d+1);
    trip.push_back(no2serial[here]);
  }
 
}

 

 

이제 방문 순서가 저장된 trip[]을 이용하여 세그먼트 트리를 구현해주어 각 구간마다 최솟값을 LCA로 구해주자.

 

 

세그먼트 트리 구현

int Init(int left, int right, int node){
  if(left == right)
    return segment_tree[node] = trip[left];
  
  int mid = (left + right)/2;
  return segment_tree[node] = min(Init(left, mid, node*2), Init(mid+1, right, node*2 +1));  
}
 
int Query(int left, int right, int query_left, int query_right, int node){
  if(right < query_left || query_right < left)
    return INT32_MAX;
  
  if(query_left<=left && right <= query_right)
    return segment_tree[node];
  
  int mid = (left + right)/2;
  return min( Query(left, mid, query_left, query_right, node * 2), Query(mid+1, right, query_left, query_right, node * 2 + 1) );
}
 

 

 

 

 

참조 서적: 알고리즘 문제 해결 전략(구종만 저), 알고리즘 트레이닝(안티 라크소넨 저)

 

코드