글 읽기 - 파이썬 메모리초과 뜹니다.

exon 1년 전 0

코드의 대략적인 설명은

1. 처음부터 1로 다 차있는지 확인하기

2. dfs를 이용해서 계속 반복해도 익지 않은 토마토가 나타나게 되는지 확인하기

3. bfs를 이용해서 답을 차례차례 구하기

입니다.

시간초과나 그냥 틀렸습니다는 이해할 수 있는데,

메모리초과는 제가 계속 새로운 배열을 만든 것도 아니고 왜 이렇게 되는지 궁금하네요.

import sys
sys.setrecursionlimit(10**6)

m, n = map(int, input().split())
arr = []
for i in range(n):
    arr.append(list(map(int, input().split())))
visited = [[False for _ in range(m)] for __ in range(n)]
k = True
r = 0

# 처음에 완성되었는가 체크
s = False
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            s = True
if not s:
    print(0)
    exit()

def dfs(y, x):
    visited[y][x] = True
    if y+1 < n and arr[y+1][x] == 0 and not visited[y+1][x]:
        dfs(y+1, x)
    if x+1 < m and arr[y][x+1] == 0 and not visited[y][x+1]:
        dfs(y, x+1)
    if y-1 >= 0 and arr[y-1][x] == 0 and not visited[y-1][x]:
        dfs(y-1, x)
    if j-1 >= 0 and arr[y][x-1] == 0 and not visited[y][x-1]:
        dfs(y, x-1)
    
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1 and not visited[i][j]:
            dfs(i, j)

s = False
for i in range(n):
    for j in range(m):
        if not visited[i][j] and arr[i][j] == 0:
            s = True
if s:
    print(-1)
    exit()

while k:
    k = False
    visited = [[False for _ in range(m)] for __ in range(n)]
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1 and not visited[i][j]:
                visited[i][j] = True
                if i+1 < n and arr[i+1][j] == 0 and not visited[i+1][j]:
                    arr[i+1][j] = 1
                    visited[i+1][j] = True
                if j+1 < m and arr[i][j+1] == 0 and not visited[i][j+1]:
                    arr[i][j+1] = 1
                    visited[i][j+1] = True
                if i-1 >= 0 and arr[i-1][j] == 0 and not visited[i-1][j]:
                    arr[i-1][j] = 1
                    visited[i-1][j] = True
                if j-1 >= 0 and arr[i][j-1] == 0 and not visited[i][j-1]:
                    arr[i][j-1] = 1
                    visited[i][j-1] = True
    r += 1
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                k = True
print(r)

siyamaki 1년 전 0

sys.setrecursionlimit(10**6)를 선언하면 그만큼 메모리를 미리 할당해 두는 걸로 알고 있습니다..

exon 1년 전 0

오오.. 유익한 정보네요

siyamaki 님께서 말씀하신대로 한번 10**5로 바꿔보았는데, 그랬더니 재귀 호출 때문에 런타임 에러가 납니다.

제가 곰곰이 생각해본 결과 dfs(재귀)를 이용해서 그런거 같은데, 처음에 확인할 때 dfs 를 bfs 로 바꾸게 되면 해결할 수 있을까요?

siyamaki 1년 전 0

bfs만 사용하여도 통과할 수 있습니다.

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

문제

문제

출처

ICPC

파이썬 메모리초과 뜹니다.

exon 1년 전 0

siyamaki 1년 전 0

exon 1년 전 0

siyamaki 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말