알고리즘 - 최소 공통 조상(Lowest Common Ancestor)

Tuna·2022년 3월 10일
0

알고리즘

목록 보기
3/3
post-thumbnail

최소 공통 조상(LCA) 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제다.

  • 위의 그래프에서 8번 노드와 15번 노드의 LCA는 2번 노드다.
  • 3번 노드와 15번 노드의 LCA는 1번 노드다.

알고리즘 수행 방법

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

Python Code

백준 11437번 정답 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e5)) # 런타임 오류 피하기
n = int(input().rstrip())

parent = [0]*(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().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
def dfs(x, depth):
    c[x] = True
    d[x] = depth
    for y in graph[x]:
        if c[y]: # 이미 깊이를 구했다면 넘기기
            continue
        parent[y] = x
        dfs(y, depth+1)

# A와 B의 최소 공통 조상을 찾는 함수
def lca(a,b):
    # 먼저 깊이(depth)가 동일하도록
    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

dfs(1,0)

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

시간 복잡도
매 쿼리마다 부모 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도가 요구된다.
따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(NM)이다.

  • 쿼리가 많아지면 정해진 시간안에 문제가 푸는 것이 불가능할 수 있다.

개선 방법
메모리를 조금 더 사용해 각 노드에 대해 2i2^i 번째 부모에 대한 정보를 기록하면 시간복잡도를 줄일 수 있다.
모든 노드에 대해 깊이(depth)와 2i2^i 번째 부모에 대한 정보를 계산한다.

시간 복잡도
매 쿼리마다 부모를 거슬러 올라가기 위해 O(logN)의 복잡도가 필요하다.
따라서 모든 쿼리를 처리할 때 시간 복잡도는 O(MlogN)이다.

개선된 Python Code

백준 11438번 정답 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(int(1e5)) # 런타임 오류 피하기
LOG = 21 # 2^20 = 1,000,000
n = int(input().rstrip())

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().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

# 루트 노드부터 시작하여 깊이(depth)를 구하는 함수
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)
    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
    # 먼저 깊이(depth)가 동일하도록
    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().rstrip())
for i in range(m):
    a,b = map(int, input().rstrip().split())
    print(lca(a,b))

참고

https://www.youtube.com/watch?v=O895NbxirM8

profile
BE 개발자가 되기 위해 노력하는 사람

0개의 댓글