글 읽기 - 파이썬) bfs 방식으로 풀었는데, 메모리초과 / 시간초과 가 떴습니다.

pmn0001 3년 전 0

pypy3 로 제출하면 메모리 초과

python3 로 제출하면 시간 초과가 떴습니다..

정석적으로 bfs를 구현했다고 생각해서 혹시 저와 같은 경우가 없나 다른 글들을 많이 읽어봤는데 같은 경우는 못봤습니다.

저는 정말 정석으로 짠 거 같은데 왜 메모리 초과가 났을까요?ㅠㅠ

import sys
from collections import deque

dx = [-1,0,1,0]
dy = [0,-1,0,1]

n, m = map(int,input().split())
mymap = list()
ans = 0

for _ in range(n):
    mymap.append(list(map(int,input())))

q = deque()
q.append((0,0))

while q:
    ans += 1
    print(q)
    for _ in range(len(q)):
        get = q.popleft()
        y,x = get[0],get[1]
        if y==n-1 and x==m-1:
            print(ans)
            sys.exit()
        mymap[y][x] = 0
        for k in range(4):
            ny = y+dy[k]
            nx = x+dx[k]
            if 0<=nx<m and 0<=ny<n and mymap[ny][nx] == 1:
                q.append((ny,nx))

mugglim 3년 전 2

시간초과 반례 드립니다.

input
3 3
111
111
111

쓴이님의 코드에서 해당 input값을 넣어 보시면,
Queue에 (1.1)이 중복으로 append되는 것을 알 수 있습니다.

해당 오류를 개선하기 위해서는 초기에 n*m크기의 check배열을 생성하여
append과정에서 checked조건을 추가하여 해결하는 방법이 있습니다.

하지만 이 방법은 메모리를 추가적으로 사용하기 때문에
다른 해결 방법을 터득하신다면 해당 방법을 사용하는 것을 추천 드립니다.

예시는 아래와 같습니다.

# check 배열 
isVisited = [[0]*m for _ in range(n)]
isVisited[0][0] = 1
    
# Queue 삽입 조건
if 0<=nx<m and 0<=ny<n and mymap[ny][nx] == 1 and\
    isVisited[ny][nx] == 0: # q추가 조건
    q.append((ny,nx))
    isVisited[ny][nx] = 1

pmn0001 3년 전 1

감사합니다! 뭐가 문제인지 이해했습니다. 즉시 처리하는 것이 아니라 큐에 담은 후에 처리를 하는 방식이라서 큐에 중복된 데이터들이 들어갔군요!! 해결방법도 감사합니다.

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

문제

문제

출처

ICPC

파이썬) bfs 방식으로 풀었는데, 메모리초과 / 시간초과 가 떴습니다.

pmn0001 3년 전 0

mugglim 3년 전 2

pmn0001 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말