글 읽기 - 파이썬 메모리 초과, 런타입에러

m16khb 4년 전 0

BFS를 활용하여 문제를 풀어보려고했습니다. 
일단 테스트 케이스는 답이 나왔습니다.
10 10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
를 넣어보니 stackoverflow가 뜹니다  재귀를 너무 깊게 들어가서 그런것 같은데
제가 어떤식으로 접근해야 할까요?

import sys
import copy
from collections import deque

sys.setrecursionlimit(4000000)

count = list()
num1, num2 = map(int, input().split())
maze = str()
for _ in range(num1):
    maze = maze + input()
visited = copy.deepcopy(maze)

q = deque()


def replace_str_index(text, index, replacement):
    return '%s%s%s' % (text[:index], replacement, text[index+1:])


def solve(cnt: int, i: int, j: int):
    global visited
    if i == num1 - 1 and j == num2 - 1:
        count.append(cnt)
        return
    visited = replace_str_index(visited, i*num2+j, 0)
    for m, n in (-1, 0), (1, 0), (0, -1), (0, 1):
        if num1 > i + m >= 0 and num2 > j + n >= 0:
            if visited[(i + m)*num2+(j+n)] == "0":
                continue
            if maze[(i + m)*num2+(j+n)] == "1":
                q.append([cnt, i+m, j+n])
    if len(q) != 0:
        temp = q.popleft()
        solve(temp[0] + 1, temp[1], temp[2])


solve(1, 0, 0)
count.sort()
print(count[0])

cheshirecoder 4년 전 0

재귀를 안 쓰면 됩니다.

m16khb 4년 전 0

아.. 재귀함수를 연습중이라서요 다른 분들도 재귀로 푸시는 것 같던데..

cheshirecoder 4년 전 0

파이썬에서 재귀는 다른 언어보다 더 주의해서 써야 합니다.

setrecursionlimit을 쓸 수 없는 경우가 생각보다 더 많습니다.

그리고 bfs를 재귀로 안 쓰는 이유는, 조금 생각해보시면 아실 듯 합니다.

재귀 해보고 싶으시면 dfs로 다시 해 보세요.

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

문제

문제

출처

ICPC

파이썬 메모리 초과, 런타입에러

m16khb 4년 전 0

cheshirecoder 4년 전 0

m16khb 4년 전 0

cheshirecoder 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말