글 읽기 - PyPy3 = 메모리 초과, Python3 = AC

sjkim200209 1년 전 0

제목 그대로 PyPy3 에서는 메모리초과 뜨고 Python3에서는 정상적으로 AC 뜨는데

이유가 궁금해서 한번 질문 올려봅니다.

import sys
from sys import stdin
sys.setrecursionlimit(10**6)

# 8방향 확인
dh = [0,1,0,-1,1,1,-1,-1]
dw = [1,0,-1,0,1,-1,-1,1]
def DFS(h,w):
    graph[h][w] = 2 #0은 땅 없음, 1은 땅 있음, 2는 땅 이미 방문함
    for i in range(8):
        a = h+dh[i]
        b = w+dw[i]
        # 지도 밖으로 나가지 않으면
        if a >= 0 and b >= 0 and a < len(graph) and b < len(graph[0]):
            # 땅이 있고 방문한 적 없으면
            if graph[a][b] == 1:
                DFS(a,b)

while True:
    # 입력
    w,h = map(int, stdin.readline().split())
    if w == 0 and h == 0:
        break
    graph = []
    for i in range(h):
        graph.append(list(map(int, stdin.readline().split())))
    #print(graph)
    
    # 섬 테스트
    landCount = 0
    for i in range(h):
        for j in range(w):
            # 땅이 있고 방문한 적 없으면
            if graph[i][j] == 1:
                DFS(i,j)
                landCount+=1
    print(landCount)

djm03178 1년 전 1

PyPy3는 기본적으로 사용하는 메모리가 큽니다. 게다가, PyPy3에서 sys.setrecursionlimit이 동작하는 원리는 그만큼의 재귀를 들어가더라도 스택 영역이 감당할 수 있을만큼 충분히 큰 크기의 메모리를 미리 확보해둔다는 뜻이기 때문에 이 수가 너무 크면 이 단계에서 바로 메모리를 너무 많이 할당받게 됩니다.

어차피 이 문제에서 들어가는 최대 재귀는 기껏해야 2500이므로 setrecursionlimit(10**4)로 해도 통과됩니다. 10**5로 해도 통과되지만, 사용된 메모리를 비교해보시면 어마어마한 차이가 나는 것을 보실 수 있습니다.

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

문제

문제

출처

ICPC

PyPy3 = 메모리 초과, Python3 = AC

sjkim200209 1년 전 0

djm03178 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말