글 읽기 - 파이썬 시간초과

jmw93 3년 전 0

log로 풀어야하는 문제는 11438번이 있어서 기본LCA 방식으로 풀었는데 시간초과가 나네용.

혹시 걸리는 부분이 있을까요? 그게아니면 파이썬 이라서 그런것이겠네요 .

한번 봐주시면 감사하겠습니다!

import sys
sys.setrecursionlimit(10**5)
n = int(input())
parent = [0]*(n+1) # 조상노드저장
d = [0] *(n+1) #depth
visit = [0]*(n+1) # 노드방문
graph=[[] for _ in range(n+1)]
ans = []


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

def dfs(node,cnt): # 루트노드부터 , 깊이를 구함
    global graph 

    visit[node] = 1
    d[node] = cnt

    for x in graph[node]:
        if visit[x] == 1: #이미 방문된 노드
            continue
        parent[x] = node
        dfs(x,cnt+1)



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

dfs(1,0) # rootnode


e = int(input()) 
for i in range(e):
    a,b = map(int,input().split())
    ans.append(lca(a,b))
for i in ans:
    print(i)
    

yellowsubmarine372 8달 전 0

dfs를 쓰시면 결국 93%에서 recrusionlimit error가 뜨더라고요(런타임에러)

BFS를 사용해 재귀 형태를 없애주는 게 좋습니다.

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

문제

문제

출처

ICPC

파이썬 시간초과

jmw93 3년 전 0

yellowsubmarine372 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말