[Python] 백준 - 11438 LCA 2

문제

N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다.

 

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

 

문제해결방법 - (서칭 참조)

 

그 전의 빌드업 문제를 풀어보았어도, 희소배열을 적용하는 개념이 이해하기가 어려웠다. 아무 참조없이 이대로 풀 수 있다면 천재..;

 

필요한 도구 

 

1) dp 2차원 배열 : log(정점의 최대갯수 100,000의 $2^{x}$의 x = log2(100000))을 행(row)으로, 정점의 갯수를 열(col)로 구성한다.

2) depth배열 : LCA알고리즘이 실행시, 깊이를 맞춰줄 때 활용된다. 최상위루트노드부터 깊이대로 저장된다.

3) dfs함수 : 초기 dp[0][1~n+1]의 배열을 저장하며, depth배열을 만들어준다.

4) v (방문리스트) : dfs함수 실행시, 방문한 노드를 체크하여 중복을 방지해준다.

 

문제해결방법

 

1. LCA알고리즘은 A) 먼저 깊이를 맞춰준 후, B) 부모노드가 맞아질 때까지 (x, y) 두 노드의 부모노드를 검색한다.

 

2. dp의 각 빈칸에는 $2^{i}$ 번째 부모노드가 저장되는 구조로 이뤄져 있다. 

 

3. dp에 행인 log2(100000)+1은 2의 지수 범위를 반복문을 돌 때 필요하다.

 

4.  $2^{i}$는 $2^{i-1}$ + $2^{i-1}$ 과 같다. 

 

5. LCA함수 실행시 깊이가 맞춰졌다면, log2(100000)+1 부터 지수를 줄여가면서 같지 않아지는 시점에 x, y를 부모노드로 갱신하여 점차 좁아지는 검색범위에서 부모노드를 찾는다.

 

1) $2^{0}$ 까지 줄여도 같아지지않았다면 결국 루트노드는 공통되는 부모노드다. 

2) 뭔가 그려놓고 따라가 보면 다 구해진다. 깊이가 큰 배열로 동작을 확인해보면 패턴을 더 정확하게 알 수 있을 것 같다.

3) 루트노드를 구하더라도, 혹시 그 밑의 공통조상이 있으면 그 노드로 선택될 수 있도록 작동된다.

 

4) 만약 큰 범위의 지수로 실행되었을 때, 부모노드가 근처의 몇 칸만 올라가도 된다면, 계속 부모노드가 if문에서 같다고 출력되어, 노드의 변화없이(큰 깊이의 노드를 유지한 채) 지수가 줄어들게 되고, 가장 가까운 공통 부모노드를 찾게될 것이다. (마치 지퍼 잠그듯이)

 

5) 큰 범위의 지수로 실행되었을 때, 예를들어 깊이가 $2^{16}$ 이고 부모노드가 중간에 위치한다면, 지수가 작아지면서 위의 부모노드는 계속 동일하다고 나오더라도, 분기되는 시점부터 $2^{4}$ , $2^{3}$ , $2^{2}$ 부분에서 값이 달라지니, 노드가 갱신되고, 지수 범위가 줄어들면서 부모노드를 찾게될 것이다. 부모노드가 그냥 바로 위에 존재한다면, $2^{0}$ 일 때, 부모노드를 찾게된다.

 

 

- 어차피 두 노드의 공통조상을 구하는 거기 때문에, 모형으로 보면 두 노드간의 족보만 보면 된다.

- 첫번째 그림은 중간과정부터라고 봐야한다. 계속 dp[i][a] != dp[i][b]라서 노드가 거슬러 올라가면서 갱신된다.

- dp[i][a] == dp[i][b]이면, 갱신되지 않고, 지수 i의 범위가 줄어든다.

 

- 코드

import sys
import math
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def dfs(idx, dep):
	v[idx] = 1
	depth[idx] = dep
	for next in graph[idx]:
		if v[next] == 0:
			dp[0][next] = idx
			dfs(next, dep+1)

def Makedp():
	dfs(1, 0)
	for r in range(1, log):
		for c in range(1, n+1):
			dp[r][c] = dp[r-1][dp[r-1][c]]
	return

def LCA(a, b):
	if depth[a] < depth[b]:
		a, b = b, a
	for i in range(log-1, -1, -1):
		if (depth[a]-depth[b]) >= (1 << i):
			a = dp[i][a]
	if a == b:
		return a
	for i in range(log-1, -1, -1):
		if dp[i][a] != dp[i][b]:
			a = dp[i][a]
			b = dp[i][b]
	return dp[0][a]

log = int(math.log2(100000))+1
n = int(input())
graph = [[] for _ in range(n+1)]
depth = [0 for _ in range(n+1)]
v = [0 for _ in range(n+1)]
dp = [[0 for _ in range(n+1)] for _ in range(log)]
for _ in range(n-1):
	a, b = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
Makedp()
m = int(input())
for _ in range(m):
	x, y = map(int, input().split())
	print(LCA(x, y))