[Python] 백준 - 3584 가장 가까운 공통 조상

문제

루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Ancestor)은 다음과 같이 정의됩니다.

• 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다.

예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다.

루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요

입력

첫 줄에 테스트 케이스의 개수 T가 주어집니다.

각 테스트 케이스마다, 첫째 줄에 트리를 구성하는 노드의 수 N이 주어집니다. (2 ≤ N ≤ 10,000)

그리고 그 다음 N-1개의 줄에 트리를 구성하는 간선 정보가 주어집니다. 한 간선 당 한 줄에 두 개의 숫자 A B 가 순서대로 주어지는데, 이는 A가 B의 부모라는 뜻입니다. (당연히 정점이 N개인 트리는 항상 N-1개의 간선으로 이루어집니다!) A와 B는 1 이상 N 이하의 정수로 이름 붙여집니다.

테스트 케이스의 마지막 줄에 가장 가까운 공통 조상을 구할 두 노드가 주어집니다.

출력

각 테스트 케이스 별로, 첫 줄에 입력에서 주어진 두 노드의 가장 가까운 공통 조상을 출력합니다.

 

 

문제해결방법 - 

 

1, LCA알고리즘를 익혀나가는 빌드업의 문제이다. dfs알고리즘으로도 풀린다.

 

1) 트리의 경우, 위에서 보여지듯 추상화된 트리 구조가 있는데, 사실 루트 노드는 어떤 노드라도 될 수 있다. 위의 트리 구조중 어떤 한 노드를 손으로 집고, 들어올린다고 생각해보자. 그 노드를  루트로 트리구조가 다시 구성될 것이다.

 

2) 문제에 주어진 노드를 루트로 dfs를 돌면서 자식노드들을 리스트에 저장하고, 뒤의 자식노드 순서대로 보면 공통 노드들이 있다. 거기서 같은 노드 중 같지 않아지는 지점에서 전에 같았던 노드가 최소공통조상이 된다. 원래의 루트노드로 보면 거꾸로 진행된다는 것을 알 수 있다.

 

2. LCA알고리즘의 경우

 

1) 트리를 구성하면서, dp[자식노드] = 부모노드 가 되도록 dp를 구성한다.

2) 여기서는 루트노드( 0의 값을 갖고 있는 1~N+1의 노드)를 찾아준 후, LCA함수를 실행한다.

 

2-1) LCA알고리즘은 노드들의 층위를 맞춰주고, 같은 층위에서 같은 노드(부모노드)가 나올 때까지 dp에 저장된 부모노드로 거슬러가는 구조를 갖고 있다.

 

(여기서 다음 문제에 나오는 희소배열을 같이 활용한 문제에서 참고할만한 정보는 다음과 같다. 

A) 층위를 맞춰준다. B) 부모노드를 찾는다.)

 

- 코드 (LCA)

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

t = int(input())

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

def LCA(a, b):
	root = 0
	for i in range(1, n+1):
		if dp[i] == 0:
			root = i
			break
	dfs(root, 0)
	while True:
		if depth[a] == depth[b]:
			break
		elif depth[a] > depth[b]:
			a = dp[a]
		else:
			b = dp[b]
	while a != b:
		a = dp[a]
		b = dp[b]
	return a

for _ in range(t):
	n = int(input())
	graph = [[] for _ in range(n+1)]
	v = [0 for _ in range(n+1)]
	depth = [0 for _ in range(n+1)]
	dp = [0 for _ in range(n+1)]
	for _ in range(n-1):
		a, b = map(int, input().split())
		graph[a].append(b)
		graph[b].append(a)
		dp[b] = a
	p1, p2 = map(int, input().split())
	print(LCA(p1, p2))

 

- 코드(DFS만 활용)

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

def dfs(x, root):
	root.append(x)
	for next in graph[x]:
		dfs(next, root)

for _ in range(int(input())):
	n = int(input())
	graph = [[] for _ in range(n+1)]
	for i in range(n-1):
		b, a = map(int, input().split())
		graph[a].append(b)
	check1, check2 = map(int, input().split())
	ans1, ans2 = [], []
	dfs(check1, ans1)
	dfs(check2, ans2)
	res = 0
	i, j = len(ans1)-1, len(ans2)-1
	while True:
		if ans1[i] != ans2[j]:
			print(res)
			break
		else:
			res = ans1[i]
		i -= 1
		j -= 1