[Python] [백준] 11438번: LCA 2

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

문제 : 11438번(lca2)
스스로 풀었는가? : x (시간복잡도 N*M인 코드로 풀어 시간 초과)

풀이

동빈나님의 강의를 참고했습니다!!
lca 강의

최소 공통 조상 찾기 알고리즘 이란

1. 모든 노드에 대한 깊이를 계산(DFS)

2. 최소 공통 조상을 찾을 두 노드를 확인

• 먼저 . 두노드의 깊이가 동일하도록 거슬러 올라간다.

• 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라간다.

3. 모든 LCA연산에 대하여 2번의 과정을 반복!

위와 같은 풀이로 해당 문제도 로직을 구현하면 되지만, 입력값이 최대 100,000개 임으로, 하나하나씩 부모를 거슬러 올라가면 시간 초과가 발생하게 됩니다...

그래서 각 노드가 거슬러 올라가는 속도를 빠르게 만드는 방법을 찾아야 합니다!

• 만약 총 15칸을 거슬러 가야하면

  • 8 -> 4 -> 2->1

• 2의 제곱 형태로 거슬로 올라가도록 하면 O(logN)의 시간 복잡도를 가질수 있습니다.

풀이 정리

그래서 노드마다 2**i번째 부모에 대한 정보까지 저장할 수 있는 parent 리스트를 만든다.

이후 각 노드의 2**i 부모 정보까지 모두 갱신하고 lca 알고리즘을 수행한다.

코드

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
LENGTH = 21

n = int(input())
parent = [[0] * LENGTH for _ in range(n + 1)]
visited = [False] * (n + 1)
d = [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):
    visited[x] = True
    d[x] = depth

    for node in graph[x]:
        if visited[node]:
            continue
        # 우선 바로 위에 있는 부모 정보만 갱신
        parent[node][0] = x
        dfs(node, depth + 1)


# 모든 노드의 전체 부모 관계 갱신하기
def set_parent():
    dfs(1, 0)
    for i in range(1, LENGTH):
        for j in range(1, n + 1):
            # 각 노드에 대해 2**i번째 부모 정보 갱신
            parent[j][i] = parent[parent[j][i - 1]][i - 1]


def lca(a, b):
    # 무조건 b의 깊이가 더 깊도록 설정
    if d[a] > d[b]:
        a, b = b, a

    # a와 b의 깊이가 동일해주도록 설정
    for i in range(LENGTH - 1, -1, -1):
        if d[b] - d[a] >= 2**i:
            b = parent[b][i]

    if a == b:
        return a

    # 올라가면서 공통 조상 찾기
    for i in range(LENGTH - 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 _ in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))

참고

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