글 읽기 - 파이썬 bfs 메모리초과 질문

zxaq15 4년 전 1

25%에서 메모리초과가 나는데 이유가 뭔가요?

그리고 아래 두 코드간의 차이가 뭔가요? 첫번째꺼는 메모리초과에러가 나느데 두번째꺼는 통과입니다.

from collections import deque


def bfs():
    global answer
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    while queue:
        x, y, ans = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < r and 0 <= ny < c:
                if matrix[nx][ny] not in ans:  # 지금까지 경로에 다음칸의 알파벳이 있는지 체크
                    next_ans = ans + matrix[nx][ny]
                    queue.append((nx, ny, next_ans))
                    answer = max(answer, len(next_ans))
    print(answer)


r, c = map(int, input().split())
matrix = []
for i in range(r):
    row = list(input())
    matrix.append(row)

start = matrix[0][0]  # 시작 알파벳
queue = deque()
queue.append((0, 0, start))  # 큐에 좌표뿐만 아니라 시작알파벳도 넣은후에 탐색할때마다 알파벳을 추가시킨다.
answer = 1  # 시작하고 아무데도 못갈수도있는경우 1이 출력되야함.
bfs()

###### 두번째 코드 #####
import sys

# 좌, 하, 우, 상
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]


def BFS(x, y):
    global answer
    q = set([(x, y, board[x][y])])

    while q:
        x, y, ans = q.pop()

        # 좌우상하 갈 수 있는지 살펴본다
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # index 벗어나지 않는지 체크하고, 새로운 칸이 중복되는 알파벳인지 체크한다
            if ((0 <= nx < R) and (0 <= ny < C)) and (board[nx][ny] not in ans):
                q.add((nx,ny,ans + board[nx][ny]))
                answer = max(answer, len(ans)+1)


R, C = map(int, sys.stdin.readline().split())
board = [list(sys.stdin.readline().strip()) for _ in range(R)]

answer = 1
BFS(0, 0)
print(answer)

wider93 4년 전 4

set은 중복을 허용하지 않습니다. 따라서 지도가

abcd

bcde

cdef

defg

라고 할 때, 첫 번째 지도는 abcdefg를 10개쯤 집어넣겠지만 아래 코드는 그렇지 않겠네요.

ycice 3년 전 0

저도 같은 고민으로 리서치 중이었는데 답변 감사합니다

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

문제

문제

출처

ICPC

파이썬 bfs 메모리초과 질문

zxaq15 4년 전 1

wider93 4년 전 4

ycice 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말