BOJ - 14502번 파이썬

DFS/BFS 문제에서 재귀 깊이 제한으로 인한 메모리 초과

백준 14502번 DFS/BFS 문제를 풀면서 일어났던 메모리초과 사태 관련해서 작성해보려고 합니다.

import sys
sys.setrecursionlimit(10**6) 관련해서 이야기 해보려고 합니다!

14502번 : 연구소

7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이런식으로 입력을 받으면 2-> 바이러스가 상하좌우로 퍼질때 울타리를 3개 세워서 최대한 안전영역 (0)을 최대값을 구하는 문제이다.

문제를 해결하기 위해 다음과 같은 접근 방식을 사용했습니다. - 참고했음

이게 연구소 최대 크기가 8이라서 최대 64칸 밖에 안되므로 완전탐색 느낌으로 진행하면 될 것 같았다.

1. 주어진 연구소 맵에서 빈 공간(0)의 위치를 모두 찾아 저장합니다.
2. 빈 공간 중 3개를 선택하여 울타리(1)를 세웁니다.(for문 사용해서 완전탐색) -> 조합구하는 느낌 바이러스 0개면 => 64C3
3. 울타리를 세운 후, 바이러스(2)의 위치에서 시작하여 BFS를 사용하여 바이러스를 퍼뜨립니다.
4. 바이러스가 퍼진 후 안전 영역(0)의 개수를 카운팅한뒤 max()비교로 최대값 갱신
5. 끝까지 반복해서 최대로 0이 많이나오는 조합의 개수 print

저는 BFS를 사용해서 풀이했는데, 처음에 고민하는 과정에서 그냥 버릇처럼

import sys
sys.setrecursionlimit(10**6)

해당 코드를 쓰면서 시작했다.

사실 이제서야 찾아보니 기본 재귀 제한이 1000이라고하는데, 이 재귀의 제한을 늘려주는 코드였다.
(크게 생각을 안해봐서 재귀니까 무한이면 그냥 무한으로 돌아가는지 알았다. 그래서 오히려 그걸 더 빨리 끝낼 수 있게 도와주는 느낌일지 알았는데 정반대였던 것이다. )

풀이코드

import sys
from collections import deque
import copy

input = sys.stdin.readline
sys.setrecursionlimit(10**6) #이거 대문에 메모리 초과???

def is_range(x,y):
    return 0<=x<n and 0<=y<m

def bfs():
    queue = deque()
    tmp_map = copy.deepcopy(box)
    for i in range(n):
        for j in range(m):
            if(tmp_map[i][j]) ==2:
                queue.append((i,j)) 

    while queue:
        x,y = queue.popleft()
        for dx,dy in zip(move_x,move_y):
            nx = x+dx
            ny = y+dy
            if(is_range(nx,ny)):
                if(tmp_map[nx][ny] == 0):
                    tmp_map[nx][ny]=2
                    queue.append((nx,ny))
    global answer
    count = 0 
    for t in range(n):
        for k in range(m):
            if(tmp_map[t][k] == 0 ):
                count+=1
    answer = max(answer,count)

def wall(count):
    if(count==3):
        bfs()
        return
    for i in range(n):
        for j in range(m):
            if(box[i][j] == 0):
                box[i][j]=1
                wall(count+1)
                box[i][j]=0



n, m = map(int,input().split())
box = [list(map(int,input().split())) for _ in range(n)]
move_x , move_y = [1,-1,0,0],[0,0,1,-1]
answer = 0 

wall(0)

print(answer)

중간 중간에 힌트도 받으면서 결과적으로는 맞는 코드인 것 같은데,계속해서 메모리 초과가 떴다.

중간의 맞았습니다.는 블로그에서 답을 보고 돌려본 코드이다 -> 육안으로는 엄청 비슷해서 같은 코드 맞나 확인차 돌려보았다.

그래서 결국 메모리 초과해결하려고 어디가 문제인지 찾아보다가,,결국 해결이 되었는데
바로 코드 상단에 추가했던 sys.setrecursionlimit(10**6) 때문이었습니다.

import sys![](https://velog.velcdn.com/images/bishoe01/post/51ee2236-d9ea-475f-85d9-efc9b216b6a2/image.png)

sys.setrecursionlimit(10**6)

setrecursion이 메모리를 잡아먹나??

sys.setrecursionlimit에 대해 다른분의 블로그를를 참고하니까 이런내용이 있었다.

sys.setrecursionlimit는 파이썬에서 재귀 호출의 최대 깊이를 설정하는 함수입니다. 재귀 호출의 깊이가 깊어지면, 스택 오버플로우(Stack Overflow) 오류가 발생할 수 있습니다. 이를 방지하기 위해 sys.setrecursionlimit 함수를 사용하여 재귀 호출의 최대 깊이를 조정할 수 있습니다. 다만, 최대 깊이를 너무 높게 설정하면, 메모리 사용량이 증가하여 프로그램의 성능이 저하될 수 있습니다. 따라서, 최대 깊이를 설정할 때에는 적절한 값을 선택하는 것이 중요합니다.

출처 - https://ctkim.tistory.com/entry/python-sys-%EB%AA%A8%EB%93%88

이처럼 sys.setrecursionlimit는 재귀 호출의 최대 깊이를 설정하는 함수이지만, 최대 깊이를 너무 높게 설정하면 메모리 사용량이 증가하여 프로그램의 성능이 저하될 수 있습니다.

아까 언급한 것처럼 파이썬의 기본 재귀 깊이 제한은 1000이며, sys.setrecursionlimit을 통해서 오히려 재귀 깊이 제한을 상향 조정하는 것이었습니다.

sys.setrecursionlimit(10**6)을 사용하면 파이썬 인터프리터에게 재귀 호출의 최대 깊이를 1,000,000으로 설정하라는 명령을 내리는 것이라고한다.

제대로 이해한게 맞다면

이번에 BFS로 해서 별로 재귀가 울타리 3개를 치기 위한 포문정도라 별로 돌아가지도 않는데 파이썬 인터프리터한테 백만번 돌 수 있게 (메모리가 할당될 수 있게) 굳이 필요없는 지시사항을 내려서 메모리 초과가 뜬 것이다 라고 이해했다..

파이썬에서 재귀 호출이 발생할 때마다 함수의 호출 정보, 지역 변수 등이 스택에 쌓이는데, 재귀 호출의 최대 깊이를 늘리면 그만큼 더 많은 메모리 공간을 스택으로 확보해야 하기 때문이다.

결론

만약 프로그램에서 재귀 호출이 많이 발생하지 않는데도 불구하고 sys.setrecursionlimit()를 사용하여 큰 값을 설정한다면, 불필요한 메모리 낭비가 발생할 수 있습니다. 이는 메모리 제한이 있는 상황에서 메모리 초과 오류를 유발할 수 있습니다.

느낀점

• 재귀 깊이 제한을 설정할 때는 실제로 필요한 만큼만 설정하고 -> 특히 이번엔 BFS로 푼만큼 더더욱 필요없는 코드였다.
• sys.setrecursionlimit()는 필요한 경우에만 사용하고, 적절한 값을 선택하는 것이 중요하다.