[python] LCA 정리(백준 11437번 : LCA, 11438번 : LCA2)

문제를 풀기 위해 앞서 알아야 할 지식은 최소 공통 조상을 찾는 LCA에 대한 개념이다. 

* LCA(Lowest Common Ancestor) 

• 트리 내에서 공통 부모인 LCA를 찾아주는 알고리즘
• 두 점 사이의 거리를 구할 때 사용한다. ( 두 노드의 공통된 조상 중에서 가장 가까운 조상 찾기 )
• 처음 트리 생성 시 각 노드마다 부모 노드와 level을 정리한다.
• 두 노드에서 올라가면서 부모 노드가 같아질 때까지 찾아간다.

 

* A와 B 두 점 사이의 거리 = 1부터 A까지의 거리 + 1부터 B까지의 거리 - 1부터 LCA까지의 거리*2

 

예를 들어, 아래와 같이 이진 트리가 주어진 경우

12번 노드와 7번 노드의 거리 = 1부터 12까지의 거리 + 1부터 7까지의 거리 - 1부터 LCA(3)까지의 거리*2

                                         = 3 + 2 - 1 * 2 = 3   

 

 

https://github.com/ndb796/python-for-coding-test/blob/master/21/5.py

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

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

11437번: LCA

[나동빈님의 LCA 기본 코드]

- O(NM)으로 해결 가능

import sys
sys.setrecursionlimit(10**5)

# 루트노드부터 시작하여 깊이를 구하는 함수
def dfs(now, depth):
    c[now] = True
    d[now] = depth

    for next_ in graph[now]:
    	# 깊이를 이미 구한 경우 무시
        if c[next_]:
            continue
        parent[next_] = now
        dfs(next_, 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(input())
arr = []
maxN = 0
for _ in range(n-1):
    x, y = map(int, input().split())
    arr.append([x, y])
    maxN = max(maxN, max([x, y]))

graph = [[] for _ in range(maxN+1)]
for x, y in arr:
    graph[x].append(y)
    graph[y].append(x)

parent = [0] * (maxN + 1)
d = [0] * (maxN + 1)
c = [0] * (maxN + 1)

dfs(1, 0) # 루트노드 1 깊이는 0
m = int(input())
for _ in range(m):
    x, y = map(int, input().split())
    print(lca(x, y))

 

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

11438번: LCA 2

[나동빈님의 LCA 심화 코드]

- 노드 번호가 1번부터 100,000번으로 주어지고 두 노드의 쌍 100,000개가 주어진 경우 위의 기본 코드로 풀 수 없음

- input = sys.stdin.readline

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5) # 재귀 깊이 설정 
LOG = 21 # 2^20 = 1,000,000

n = int(input())
parent = [[0]*LOG for _ in range(n+1)] # 부모 노드 정보
d = [0] * (n+1) # 각 노드까지의 깊이
c = [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, depth):
    c[x] = True
    d[x] = depth

    for y in graph[x]:
        if c[y]:
            continue
        parent[y][0] = x
        dfs(y, depth + 1)

# 전체 부모 관계를 설정하기
def set_parent():
    dfs(1, 0) # 루트노드 1번부터 시작 
    for i in range(1, LOG):
        for j in range(1, n+1):
            parent[j][i] = parent[parent[j][i-1]][i-1]

# A와 B의 최소 공통 조상 찾기 
def lca(a, b):
    # B가 더 깊도록 설정 
    if d[a] > d[b]:
        a, b = b, a
    # 깊이가 동일하도록 
    for i in range(LOG - 1, -1, -1):
        if d[b] - d[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))