[백준][BOJ11438] LCA2 (with. DFS)

1. 문제 : https://www.acmicpc.net/problem/11438

11438번: LCA 2

---

2. 풀이 : LCA + 오일러 투어 테크닉

---

3. 시간복잡도 : O(MlogN)

---

4. 설명

문제의 예시를 그림으로 표현하면 그림[1]과 같다.

그림[1]

루트(1번)에서부터 오일러 투어 테크닉을 사용하여 각 노드들의 진입/진출 순서를 확정한다. 

그림[2]

그림[2]에서 진입 순서 배열을 in이라고 하고 진출 순서 배열을 out이라고 하였을 때, 두 노드 a와 b에 대하여 다음이 성립한다.

1. in[a] <= in[b] && out[a] >= out[b] 라면 a는 b의 조상이다. (그림[3])

그림[3]

2. in[a] > in[b] || out[a] < out[b] 라면 a는 b의 조상이 아니다. (그림[4], 그림[5])

그림[4]

그림[5]

오일러 투어를 진행하며 그림[6]과 같이 각 노드들의 2^0번째 조상, 즉 부모 노드를 확정한다.

그림[6]

루트 노드의 부모인 '-1'값은 조상이 없음을 의미한다.

그림[7]

희소 배열을 sparse라고 했을 때, 아래의 식이 성립하며 그림[7]과 같이 각 노드의 나머지 조상 값들을 채워 넣을 수 있다.

sparse[a][n] = sparse[sparse[a][n-1]][n-1]

a와 b의 최소 공통 조상을 찾는 과정은 아래와 같다.

    1-1. a가 b의 조상이라면, a와 b의 최소 공통 조상은 a이므로 탐색을 종료한다.

    1-2. a가 b의 조상이 아니라면, n의 값을 가장 큰 값부터 0까지 1씩 줄여가며 a의 2^n번째 조상의 값이 나올 때까지 탐색한다.

    2-1. a의 2^n번째 조상이 b의 조상이라면 탐색을 재개한다.

    2-2. a의 2^n번째 조상이 b의 조상이 아니라면, a의 위치를 2^n번째 조상 노드로 변경하고, 변경된 a와 b의 최소 공통 조상을 탐색한다.

    3. n이 0이 되었을 때 탐색을 종료하며, 그때의 a의 부모 노드가 최소 공통 조상이 된다.

15(a)와 14(b)의 최소 공통 조상을 찾는 경우를 예시로 보자. n의 가장 큰 값부터 1씩 줄여가며 탐색을 했을 때, 15의 조상이 14의 조상이 안 되는 최초의 경우는 그림[8]과 같이 n이 1인 경우이다.

그림[8]

a의 위치를 15에서 5로 변경하고 탐색을 재개한다. 이때, n의 값은 0이며 5의 2^0번째 조상인 2 역시 14의 조상이 아니므로 a의 위치를 2로 변경한다.

그림[9]

n이 0일 때까지 탐색을 하였으므로, 탐색을 종료하며 이때 a의 위치는 그림[10]과 같다. 탐색이 종료되었을 때 sparse[a][0] 즉, sparse[2][0] 값이 15와 14의 최소 공통 조상이 되며 그 값은 1이다.

---

5. 코드