[Python] 11437번 LCA

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

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

N=int(input()) # 노드 개수

# 그래프 정보 저장하기
graph=[[] for _ in range(N+1)]
for _ in range(N-1):
    v,u=map(int,input().split())
    graph[v].append(u)
    graph[u].append(v)

parent=[0]*(N+1) # 각 노드의 이전 부모
d=[0]*(N+1) # 각 노드의 루트까지의 거리
visited=[0]*(N+1) # 각 노드의 방문 표시

# 각 노드의 깊이 구하기
def dfs(x,depth): 
    visited[x]=True
    d[x]=depth
    for y in graph[x]:
        if visited[y]: # 방문했으면 넘어가기
            continue
        parent[y]=x
        dfs(y,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

dfs(1,0)

M=int(input()) # 가장 가까운 공통 조상을 알고싶은 쌍의 개수
for _ in range(M):
    a,b=map(int,input().split())
    print(LCA(a,b))

 

`sys.setrecursionlimit`를 설정해주지 않으니까 런타인 에러가 났는데 추가하니 해결되었다.

근데 `sys.setrecursionlimit`를 꼭 해야하나?

이는 문제에서 N의 조건이 2 ≤ N ≤ 50,000으로 만약 편향 트리(skewed tree)일 경우 DFS 호출 깊이가 최악에서 50,000까지 갈 수 있기 때문이다. 파이썬의 기본 재귀 한도는 약 1,000이기 때문에 DFS를 하면 무조건 재귀 깊이 초과가 발생한다. 때문에 `sys.setrecursionlimit`을 통해 recursionlimit을 증가가 필수적이다.