글 읽기 - 11437 LCA 파이썬 런타임 에러

jangky000 4년 전 0

LCA 유형의 문제를 처음 접해봐서 다른 언어를 참고하여 코드를 작성해보고 있습니다.

파이썬으로 풀어보고 싶은데, 파이썬으로 LCA를 구현한 코드를 찾지 못했습니다.

채점 시간이 오래 걸리기도 하고, 결과적으로 런타임 에러가 발생하는데 제 코드에 분명히 잘못된 부분이 있을 것이라 생각합니다.

어떤 부분을 개선해야하는지 조언 부탁드립니다.

# 재귀로 인한 런타임 에러 발생 시 추가,
import sys
sys.setrecursionlimit(100000)

# LCA(Lowest Common Ancestor) 같은 조상 찾기

# 최소 공통 부모는 트리의 같은 깊이에 있다.***

# 1. 노드 다 입력 받기 입력[부모] = 자식
# 2. 노드 1을 기준으로 트리 만들며 깊이도 구하기 / (해시구조로), 트리[자식] = (부모, 깊이)
# 3. 깊이가 낮은 것을 기준으로 트리를 올라감
# 4. 같은 부모가 나올 때까지

# 주의: 
# 부모/자식 중 어떤 노드가 먼저 나올지 모른다.
# 부모/자식 자식/부모로 입력을 받는다
# 1에서부터 DFS하면서 중복 방문을 제거
# 입력을 받은 후 트리를 만들어야 하는 이유: 어떤 노드가 부모 노드인지 모르기 때문에, 관계를 정리하기 위해서

N = int(input())
temp = {}
visited = {}
tree = {}

for i in range(N-1):
    node1, node2 = map(int, input().split())
    if node1 in temp.keys():
        temp[node1].append(node2)
    else:
        temp[node1] = [node2]

    if node2 in temp.keys():
        temp[node2].append(node1)
    else:
        temp[node2] = [node1]

    visited[node1] = 1
    visited[node2] = 1
    
# 트리 만들기
def dfs(root, depth):
    # 1은 계산하지 않도록 처리
    global temp, tree, visited
    for node in temp[root]:
        if node in visited:
            visited.pop(node)
            tree[node] = (root, depth)
            dfs(node, depth+1)
            if not visited:
                return

visited.pop(1) # 1은 루트이므로 트리에서 제거한다.
dfs(1, 1)

# print(tree)

M = int(input())

for i in range(M):
    search1, search2 = map(int, input().split())
    # print('s1', tree[search1][1])
    # print('s2', tree[search2][1])

    while tree[search1][1] != tree[search2][1]:
        if tree[search1][1] > tree[search2][1]:
            search1 = tree[search1][0]
        else:
            search2 = tree[search2][0]
    # print('s1', tree[search1])
    # print('s2', tree[search2])

    while True:
        if search1 == search2:
            print(search1)
            break
        else:
            search1 = tree[search1][0]
            search2 = tree[search2][0]

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

11437 LCA 파이썬 런타임 에러

jangky000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말