[백준]11437 LCA(Python)

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

11437번: LCA

 

문제 접근

 

LCA(Lowest Common Ancestor): 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제

LCA 예시 트리

 

♣ 동작 방식

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

 

♥시간 복잡도 

• 만약 한쪽에 치우쳐서 일렬로 된 노드인 경우 부모 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도가 요구된다.
• 만약 M개의 쌍이 주어진다면 이때 시간 복잡도는 O(NM)이다. 

++ (dfs 코드 먼저 이해)

# 루트 노드부터 시작하여 깊이를 구하는 함수
def dfs(x, depth):
    visited[x] = True
    d[x] = depth
    for i in graph[x]:  # 노드 x와 연결된 모든 인접 노드에 대해 반복
        if visited[i]:
            continue
        parent[i] = x   # 노드 y의 부모 노드를 x로 설정
        dfs(i, depth+1)
        
n = int(input())

graph = [[] for _ in range(n+1)]
parent = [0] * (n+1)
d = [0] * (n+1)
visited = [0] * (n+1)

for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dfs(1, 0)
print(d)

 

코드

import sys
sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기

n = int(input())    # 노드의 개수 입력


parent = [0] * (n+1)
d = [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, depth):
    visited[x] = True
    d[x] = depth
    for i in graph[x]:  # 노드 x와 연결된 모든 인접 노드에 대해 반복
        if visited[i]:
            continue
        parent[i] = x   # 노드 y의 부모 노드를 x로 설정
        dfs(i, depth+1)

# a, b의 최소 공통 조상을 찾는 함수
def lca(a, b):
    # 깊이(depth)가 같아지도록
    while d[a] != d[b]:
        if d[a] > d[b]:
            a = parent[a]   # a의 깊이가 b의 깊이보다 크면 a야 위로 올라오렴
        else:
            b = parent[b]   # b의 깊이가 a의 깊이보다 크면 b야 위로 올라오렴
    # 노드가 같아지도록(부모 노드가 같아져야 해!!)
    while a != b:
        a = parent[a]
        b = parent[b]

    return a

dfs(1, 0)   # 1번 노드가 루트 노드, 깊이 0

m = int(input())

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

 

문제 회고

 

Python3로 돌리니까 시간 초과가 떠서 PyPy3로 돌렸다. 

시간 초과가 발생할 수 있는 부분이 깊이가 같아지도록 올라오는 반복문 or 노드가 같아지도록 올라오는 반복문 때문인 것 같은데 이를 개선할 수 있는 방식을 따로 정리해 봐야겠다.