[백준][Python] 11437번 LCA

11437번: LCA

 

 

코드

import sys
sys.setrecursionlimit(100000)
def dfs(num,dep):
	visit[num] = 1
	d[num] = dep
	for i in tree[num]:
		if visit[i] == 1:
			continue
		par[i] = num
		dfs(i,dep+1)

def parent(a,b):
	while d[a] != d[b]:
		if d[a] < d[b]:
			b = par[b]
		else:
			a = par[a]
	while a != b:
		a = par[a]
		b = par[b]
	return a

n = int(input())
tree = [[] for _ in range(n+1)]
d = [0] * (n+1)
visit = [0] * (n+1)
par = [0] * (n+1)
for _ in range(n-1):
	a,b = map(int,sys.stdin.readline().split())
	tree[a].append(b)
	tree[b].append(a)
m = int(input())
dfs(1,0)
for _ in range(m):
	a,b = map(int,sys.stdin.readline().split())
	print(parent(a,b))

 

설명

LCA 알고리즘을 사용하는 문제는 처음 풀어봐서 다른 사람의 풀이를 찾아봤다..

먼저 주어진 입력값으로 양방향 그래프를 생성한다. 

그리고 dfs를 사용하여 각 노드의 depth와 부모 노드를 각각 d와 par 배열에 저장한다.

두 정점을 입력받으면 먼저 두 노드의 depth가 같게 만들어주고 조상이 같아질 때까지 각 노드의 부모 노드를 따라 거슬러 올라간다.