junyub2   2년 전

아래와 같이 dfs코드를 만들어봤습니다. 재귀함수로 인해 런타임에러가 발생했다고 하는데 어떻게 해결을 해야되는지 감이 잡히지 않습니다. 도움 부탁드립니다

import sys
from collections import defaultdict

n, m, k, x = map(int, sys.stdin.readline().split())
dic = defaultdict(list)

for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    dic[a].append(b)

def dfs(lst, x, visited):
    visited[x] = True

    for i in lst[x]:
        count[i] = count[x] + 1
        if not visited[i]:
            dfs(lst, i, visited)

visited = [False] * (n+1)
count = [0] * (n+1)
dfs(dic, x, visited)

for i in range(len(count)):
    if count[i] == k:
        print(i)
if k not in count:
    print(-1)

limepencil   2년 전

재귀함수 문제라면 sys.setrecursionlimit(10**9) 같은 식으로 재귀함수 호출제한을 늘려줄수 있습니다

junyub2   2년 전

감사합니다 덕분에 또 새로운 걸 알아가네요

근데 3번째 줄에 sys.etrecursionlimit(1000000) 집어넣었는데 틀렸다고 나오네요. 혹시 제가 작성한 코드에서 문제 될만한게 어떤게 있을까요? 프로그램에서는 정상적으로 돌아가서 뭐가 문제인지 알수가 없네요 ㅠㅠ

limepencil   2년 전

음 저라면 BFS를 사용할것 같습니다. k 가 넘어가면 바로 bfs 종료 시켜주는 방식으로 하면 k 일때까지만 탐색을 하고 그뒤로는 안하기 때문에 시간을 DFS보다 줄일수 있습니다. 그리고 pypy로 제출해보세요. 보통 시간이 파이썬에서 막히면 pypy에서 되는 경우도 많습니다

limepencil   2년 전

그냥 아마 pypy로 돌리면 통과할것 같긴 한데 dfs를 재귀적 말고 비재귀로 구현하시면 재귀 제한없이 더 빨리 돌아갑니다.(시간은 항상 비재귀가 재귀보다 빠릅니다)

junyub2   2년 전

bfs가 시간이 더 줄여진다는건 몰랐네요. 역시 사람들이 괜히 bfs로 푸는게 아니였나보구나.. 덕분에 몰랐던 개념들까지 배웠습니다 감사합니다 !

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