https://www.acmicpc.net/problem/11437
시간 3초, 메모리 256MB
input :
- N (1 ≤ N ≤ 50,000)
- N-1개 줄에는 트리 상에서 연결된 두 정점
- M(1 ≤ M ≤ 10,000)
- M개 줄에는 정점 쌍이 주어진다.
output :
- 두 정점의 가장 가까운 공통 조상을 출력
조건 :
-
트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
-
두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력하시오.
학교에서 LCA를 배우면서 풀어보게 된 문제이다.
순서
기본적으로 해야 하는 순서가 존재한다.
(root를 모르는 경우)
1. find연산을 통해 루트를 찾는다, 또는 작은 노드를 parent로 만드는 방식으로 루트를 만든다.
2. 모든 노드의 깊이를 알아야 한다.
2 - 1. 깊이를 기록하는 과정은 dfs로 구현하는 것이 매우 편하다.
2 - 2. 이 과정에서 자기 부모의 노드를 기록하게 하여 나중에 찾을 수 있도록 한다.
3. lca
3 - 1. 우선 깊이를 동일하게 만든다.
3 - 2. 동일한 노드인지 확인하고 그렇지 않다면 계속 1 레벨씩 올라가도록 한다.
위의 과정을 순서대로 한다면 2가지 경우가 발생한다.
두 정점이 동일하거나 동일한 부모를 가지는 경우가 그것이다.
동일한 부모를 가지고 있는 경우 return에서는 parent에 저장된 값을 출력하게 하면 된다.
import sys
sys.setrecursionlimit(100000)
def dfs(node, depth):
visit[node] = True
d[node] = depth
for next_node in graph[node]:
if visit[next_node] == 1:
continue
parent[next_node] = node
dfs(next_node, depth + 1)
def lca(a, b):
while d[a] != d[b]:
if d[a] > d[b]:
a = parent[a]
else:
b = parent[b]
while a != b:
a = parent[a]
b = parent[b]
return a
n = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]
parent = [0] * (n + 1)
d = [0] * (n + 1)
visit = [0] * (n + 1)
for i in range(n - 1):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
dfs(1, 0)
m = int(sys.stdin.readline())
for i in range(m):
a, b = map(int, sys.stdin.readline().split())
print(lca(a, b))
