백준 11437번 <LCA>

백준 알고리즘 11437번

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

11437번: LCA

---

11437번

N개의 정점으로 이루어진 트리가 있을 때, 두 정점에 대해 가장 가까운 공통 조상을 구하여라.

 

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

 

출력으로 M개의 줄로 들어온 두 정점의 가장 가까운 공통 조상을 출력한다.

---

문제 해결

최소 공통 조상 알고리즘을 통해 해결할 수 있다.

최소 공통 조상 알고리즘은 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 것이다.

 

최소 공통 조상 알고리즘

1. 모든 노드에 대해 깊이(depth)를 계산
2. 최소 공통 조상을 찾을 두 노드를 확인
   1. 먼저 두 노드의 깊이가 동일하도록 거슬러 올라간다.
   2. 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다.

이때, 더 빠르게 하기 위해 각 노드에 대해 2^i번째 부모에 대한 정보를 기록하여 시간 복잡도를 개선한다,

---

코드

import sys
input = sys.stdin.readline

sys.setrecursionlimit(int(1e5))
LOG = 21

n = int(input())
parent = [[0] * LOG for _ in range(n+1)]
depth = [0] * (n+1)
visited = [0] * (n+1)

graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def dfs(x, d):
    visited[x] = True
    depth[x] = d
    for y in graph[x]:
        if visited[y]:
            continue
        parent[y][0] = x
        dfs(y, d + 1)
def set_parent():
    dfs(1, 0)
    for i in range(1, LOG):
        for j in range(1, n+1):
            parent[j][i] = parent[parent[j][i-1]][i-1]
            
def LCA(a, b):
    if depth[a] > depth[b]:
        a, b = b, a
    for i in range(LOG-1, -1, -1):
        if depth[b]- depth[a] >= (1 << i):
            b = parent[b][i]
    if a == b:
        return a;
    for i in range(LOG-1, -1, -1):
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]
    return parent[a][0]

set_parent()
m = int(input())
for i in range(m):
    a, b = map(int, input().split())
    print(LCA(a, b))

 

 

parent[j][i] = j번 노드의 2^i 위의 조상을 의미

depth[i] = i번 노드의 깊이

visited[i] = 깊이를 구할 때, i번 노드를 방문했는지를 알기 위해 사용

graph[i] = i번 노드와 연결된 노드들의 list

 

dfs(x, d) 함수

x번 노드의 깊이를 구하는 함수. x번 노드와 연결된 노드들을 기준으로 dfs를 다시 호출한다.

 

set_parent()

각 노드들의 조상들을 채운다.

 

LCA(a, b)

a와 b노드의 가장 가까운 공통 조상을 찾아서 반환한다.

---

결과

---