Problem

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

Python Code

from sys import stdin

def find_parent(parent, x):
	result = [x]
	while parent[x]:
		result.append(parent[x])
		x = parent[x]
	return result

T = int(stdin.readline())

for _ in range(T):
	N = int(stdin.readline())
	parent = [0] * (N + 1)
	for _ in range(N - 1):
		A, B = map(int, stdin.readline().split())
		parent[B] = A
	x, y = map(int, stdin.readline().split())
	x_parent = find_parent(parent, x)
	y_parent = find_parent(parent, y)
	ans = x_parent[-1]
	while x_parent and y_parent and x_parent[-1] == y_parent[-1]:
		ans = x_parent.pop()
		y_parent.pop()
	print(ans)

Solution

• 트리에서 가장 가까운 공통 조상을 찾는 문제이다
• parent 리스트에 B 노드의 부모 노드를 저장한다
  - parent[B] = A
• 공통 조상을 구할 x와 y의 모든 부모 노드를 x_parent, y_parent에 저장한다
• 두 리스트의 마지막 값은 루트노드이며 루트노드부터 시작해서 한 리스트의 값이 없어지거나 값이 다른 노드가 나올 때까지 리스트의 값을 pop한다
• 값이 다른 부모노드를 만나거나 한 노드의 부모노드를 모두 탐색한 경우 마지막으로 pop한 노드가 공통 조상이므로 ans에 저장한 값을 출력한다
• 루트노드 부터 탐색하는 것이 아닌 주어진 노드의 부모노드부터 탐색하는 방법도 있다
  - 부모노드부터 탐색하기 위해서는 먼저 두 노드의 부모노드의 깊이를 맞추고 시작한다
  - 반대로 다른 노드일 동안 탐색을 계속하고 처음으로 같은 노드를 만난다면 그 노드가 공통 조상이 된다