[백준 11437] 최소 공통 조상(LCA) 알고리즘(기본) - 파이썬(Python)

LCA

문제

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

입력

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

출력

M개의 줄에 차례대로 입력받은 두 정점의 가장 가까운 공통 조상을 출력한다.

예제 입력 1

15
1 2
1 3
2 4
3 7
6 2
3 8
4 9
2 5
5 11
7 13
10 4
11 15
12 5
14 7
6
6 11
10 9
2 6
7 6
8 13
8 15

예제 출력 1

2
4
2
1
3
1

---

최소 공통 조상(least common ancestor)

최소 공통 조상 : 트리 그래프에서 임의의 노드를 선택했을때, 거슬러 올라가면서 부모를 탐색할때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상 (LCA)이라고 합니다.

 

1. 인접 리스트로 트리 데이터를 저장

2.bfs/dfs로 각 노드의 트리 깊이를 수합니다

예를 들어 bfs로 깊이와 부모노드를 각각 구한후, 부모노드 리스트 parant 리스트를 작성해줍니다.

노드	1	2	3	4	5	6	7	8	9
부모노드	0	1	1	2	2	3	3	4	4

위에 표에서 한 노드가 부모노드로 한칸 올라가는 과정은 아래와 같습니다.

a = 9

a= parant[a]

a=parant[9]

a=4

위와 같은 과정으로 한칸한칸씩 부모노드로 올릴 수 있습니다.

 

3. 깊이를 똑같이 맞춰줍니다 - 깊이가 큰 노드를 그 차이만큼 반복합니다

제 코드에서는 a,b 노드를 받으면 a가 항상 깊이가 크도록 b가 더 큰 경우 a,b를 교환했습니다.

a의 깊이 - b의 깊이를 통해서 깊이의 차이를 구한후, 그만큼 a의 부모노드로 올라가는 연산을 해줍니다.

 

4.두 노드를 동시에 부모 노드로 올라가면서 최소 공통 조상을 찾는다

깊이를 똑같이 맞춰준 후에는, 한칸씩 올라가서 똑같은 부모노드가 올때까지 a,b의 값을 부모노드로 새로고침 해줍니다.

---

파이썬 코드

인접 리스트를 tree에 넣고, depth를 깊이 테이블로, 자식노드의 깊이는 부모노드의 깊이보다 1만큼 크므로 bfs탐색할때 이용했습니다.

 

제출하실때 Python말고 PyPy3로 제출해야합니다!

 

일단 이번에 배운 알고리즘은 LCA 기본 알고리즘이고

 

2의 k승씩 탐색해서 훨씬 더 빠르게 구하는 알고리즘은 다음 포스트에서 알려드리겠습니다 (백준 11438)

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
tree  = [[]for _ in range(n+1)]
depth = [0] * (n+1)
parant = [0] * (n+1)
visited = [False] * (n+1)
for _ in range(n-1):
    s,e = map(int, input().split())
    tree[s].append(e)
    tree[e].append(s)

def bfs(s):
    queue = deque()
    queue.append(s)
    while queue:
        node = queue.popleft()
        visited[node] = True
        for i in tree[node]:
            if not visited[i]:
                depth[i] = depth[node] + 1
                parant[i] = node
                queue.append(i)

def LCA(a,b):
    if depth[a] < depth[b]:
        temp = a
        a=b
        b=temp
    diff = depth[a] - depth[b]
    for _ in range(diff):
        a = parant[a]
    while a!=b:
        a = parant[a]
        b = parant[b]
    return a

bfs(1)

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