글 읽기 - 파이썬 재귀 한도에 관해 질문드립니다.

dusrlf13 3년 전 1

런타임 에러 문제를 뿜다가 keenshark님의 글을 보고 재귀 한도를 넉넉히 설정하니 해결이 되더라구요.

sys.getrecursionlimit() 을 통해 재귀 한도를 늘려주지 않았을 때의 재귀 한도를 출력해보니 1000이 나왔습니다.

문제의 조건에서 가로와 세로의 길이 한도가 50이라 재귀가 최대 2500까지 발생할 것이라 생각해보고 setrecursionlimint()을 통해 재귀한도를 조여줘 봤는데 2502에서도 통과가 안되고 2503에서 통과가 됩니다.

이 문제에서 재귀한도가 굳이 2503에서 통과되는 이유가 뭘까요???

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

생각해보니 테스트 케이스의 반복수와도 관련이 있다는 생각이 드는데...정확하진 않네요 ㅠㅠ 만약 맞다면 테스트 케이스의 수에도 조건이 필요하지 않을까요?!

# 유기농 배추
import sys
sys.setrecursionlimit(2503)

def dfs(par_y, par_x):
    if par_x >= M or par_y >= N or par_x <= -1 or par_y <= -1:
        return False
    elif graph[par_y][par_x] == 1:
        graph[par_y][par_x] = 0
        dfs(par_y+1, par_x)
        dfs(par_y-1, par_x)
        dfs(par_y, par_x+1)
        dfs(par_y, par_x-1)
        return True
    else:
        return False

result = []
count = 0

T = int(input())

for _ in range(T):
    # 가로길이 M, 세로길이 N, 배추가 심어진 위치의 개수 K
    M, N, K = map(int, input().split())

    graph = [[0] * M for _ in range(N)]

    for _ in range(K):
        x, y = map(int, input().split())
        graph[y][x] = 1

    # Test Case 수 만큼 돌리기
    for k in range(T):
        for i in range(M):
            for j in range(N):
                if dfs(j, i) == True:
                    count += 1
    
    result.append(count)

    graph = [[0] * M for _ in range(N)]
    count = 0

for node in result:
    print(node)

dongwoo338 3년 전 0

파이썬에서의 재귀 한도가 어떻게 되는지는 잘 모르겠지만. 2500 정도의 재귀는 그렇게 크지 않기 떄문에 충분히 가능할 것이라고 생각됩니다.

테스트케이스에 대해서는 각 테스트케이스 마다 새로운 함수가 호출되므로 재귀한도에 관해서는 상관이 없을 것으로 보입니다.

왜 2503부터 통과가 되는지는 모르겠으나 한도를 제한보다는 조금 크게 넉넉하게 잡아주는 것이 좋다고 생각합니다.

dongwoo338 3년 전 0

다른 분들의 코드를 좀더 찾아보니 재귀한도가 기본 1000이라 재귀한도를 10**6등의 큰 수로 임의로 크게 두고 시작하는 식으로 많이 짜시네요

2500 정도의 재귀는 그렇게 크지 않기 떄문에 충분히 가능할 것이라고 생각됩니다. (<-- 이부분에 대해서 수정합니다 ㅜ)

doju 3년 전 3

마지막 칸을 방문 체크한 뒤에도 네 방향을 한 번 더 확인하므로 재귀는 최대 2501번 들어가게 됩니다.
프로그램을 실행시키기 위해서 기본적으로 call stack이 조금 사용됩니다. 이 프로그램(Ideone)의 에러 메시지를 보면 별도의 함수에 들어가지 않았는데도 재귀 깊이(recursion depth)가 2로 세어지는 것을 확인할 수 있습니다. 프로그램의 시작 시점에 재귀 깊이가 얼마일지는 환경에 따라 다를 수 있습니다.

따라서 BOJ의 실행 환경이 위의 사이트와 같이 재귀 깊이를 2부터 센다면, 재귀 한도는 질문하신 대로 적어도 2503 이상으로 잡아야 합니다.

이와 같이 재귀의 깊이는 정확히 세기 어려울 뿐더러 시스템에 의존하는 부분이 있고, 또한 한도를 크게 잡아서 손해를 볼 일이 없기 때문에 Python으로 문제를 푸시는 분들은 보통 한도를 임의의 큰 값으로 설정해 놓고 크게 신경쓰지 않습니다.

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

문제

문제

출처

ICPC

파이썬 재귀 한도에 관해 질문드립니다.

dusrlf13 3년 전 1

dongwoo338 3년 전 0

dongwoo338 3년 전 0

doju 3년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말