[Python] sys.setrecursionlimit

문제 상황

dfs를 사용하여 재귀를 사용하는 문제를 푸는데, 입력값이 큰 테스트케이스에서 recursionError: maximum recursion depth exceeded 오류가 생겼다.

sys.setrecursionlimit

파이썬의 재귀 깊이 제한은 1000이다. 따라서 재귀로 문제를 풀이할 때 1000번의 재귀를 넘으면 recursionError: maximum recursion depth exceeded 오류가 뜬다. 그래서 sys.setrecursionlimit(N) 을 작성하여 재귀 깊이 제한을 직접 설명해줘야 한다.

문제에서 입력에 따라 최대 안전지대의 크기는 N x M(1≤N,M≤50)이 되기 떄문에 최소 2500의 recursion limit이 필요하다. 이 방법을 쓰지 않는다면 bfs알고리즘을 활용하거나 dfs알고리즘을 재귀방식이 아닌 비재귀방식으로 구현해야 한다.

향후 재귀를 사용하는 상황에서 테스트케이스 오류를 방지하기 위해 sys.setrecursionlimit를 작성하고 문제를 풀어야 함을 배웠다.

적용 코드

import sys

N, M = list(map(int, input().split()))
grid = [list(map(int, input().split())) for _ in range(N)]
visited = [[False for _ in range(M)] for _ in range(N)]
k = 1
safe_area = 0
max_area = 0
best_k = 1
sys.setrecursionlimit(3000)

def in_range(x, y):
    return 0 <= x and x < N and 0 <= y and y < M

def can_go(x, y):
    if not in_range(x, y):
        return False
    if visited[x][y] or grid[x][y] <= k:
        return False

    return True

def dfs(x, y):
    dxs, dys = [0, 1, 0, -1], [1, 0, -1, 0]
    for dx, dy in zip(dxs, dys):
        new_x, new_y = x + dx, y + dy

        if can_go(new_x, new_y):
            visited[new_x][new_y] = True
            dfs(new_x, new_y)

def all_flood(k):
    for i in range(N):
        for j in range(M):
            if grid[i][j] > k:
                return False

    return True

while not all_flood(k):
    safe_area = 0
    visited = [[False for _ in range(M)] for _ in range(N)]

    for i in range(N):
        for j in range(M):
            if can_go(i, j):
                visited[i][j] = True
                dfs(i, j)
                safe_area += 1

    if safe_area > max_area:
        max_area = safe_area
        best_k = k
    elif safe_area == max_area:
        best_k = min(best_k, k)

    k += 1

print(best_k, max_area)