[C++] 코딩테스트 대비 - 트리 알고리즘(LCA)

Coding Interview/빈출유형 정리

2로 접어듦 2023. 2. 4. 18:12

Tree Algorithm

가장 낮은 공통 조상 구하기 문제: 두 정점 사이의 최단 거리를 빠르게 찾을 수 있다.

선형탐색(O(N))의 방식과 이분탐색(O(logN))의 방식이 있음.

선형 탐색은 두 노드의 깊이를 같게 한 뒤 선형적으로(차례로) parent A == parant B 인지 확인하는 방법.

parent[노드 A]를 1차원 배열에 저장하여 선형적으로 탐색한다.

이분탐색은 노드별 parent 정보를 2차원배열에 저장하는 것. parent[노드번호 A][노드 A의 2의 k승 거리에 있는 부모노드]

즉, parent[A][T] = 노드 A의 2^T 번째 조상.

ex. parent[13][0] = 9, parent[13][1] = parent[9][0] = 5, parent[13][2] = 1
이 2차원 배열을 dfs 하는 과정으로 O(log N)을 만든다.

이분탐색을 위한 수행 알고리즘

트리는 vector<vector<int>> 로 구현한다(무방향 그래프)
모든 노드들의 depth 정보를 탐색한다.
DFS알고리즘(재귀적 호출 + visited)을 이용하여 노드 번호와 depth를 파악하고 기록한다.
+ 거리가 0인 parent 노드를 초기화한다.(parent[next_node][0] = cur_node)
LCA를 위한 parent[][] 배열을 작성한다.
위의 이분탐색 알고리즘을 이용하여 채워나간다. parent[u][t] = parent[parent[u][t-1]][t-1] 이다.
ex. parent[13][1] = parent[9][0]
for t /n for u /n parent[u][t] = parent[parent[u][t-1]][t-1] 로, 높이가 낮은 것에 대해 전체 노드를 먼저 작성한 후 다음 높이로 넘어가는 방식을 사용한다.
두 노드 U, V 의 depth 를 맞춰준다.
depth[U] != depth[V]일 때, |depth[U] - depth[V]| = 15 일때, 15 = 1111(2) 이므로, 2^0, 2^1, 2^2, 2^3 으로 부모를 따라가면, logN 번 비교하여 depth[U] == depth[V]를 만들 수 있다.
같아지면, 부모를 따라 올린 노드 U 를 반환한다.
parent를 탐색한다.
parent[U][T] != parent[V][T] 이면 LCA는 T보다 멀리 있는 것이다.
parent[U][T] != parent[V][T] && parent[U][T+1] == parent[V][T+1] 이면 LCA는 2^T ~ 2^(T+1) 사이에 존재한다.
따라서 T를 큰 값부터 하나씩 내려가며 위 조건에 맞을 경우를 찾는다. 맞을 때, U와 V를 2^T만큼 올려준다.
parent[U][0]이 정답이 된다.