글 읽기 - #1987 python 메모리초과 어떻게 해야될지 모르겠습니다.

tkqlzz 7년 전 0

가로 세로 최대 20밖에 안되길래 간단할줄 알았는데 메모리초과에서 걸리네요

BFS 방식으로 QUEUE에 좌표랑 방문된 데이터를 추가하는 방식으로 짰습니다..

pop에서 속도가 느려질거같아 deque를 사용햇구요 20x20인데도 경우의수가 엄청많나봅니다..

다른방법을 써야되나요??

deque 안쓰고 data에 들어가는 메모리를 줄이고자 재귀로 dfs탐색을 하면 시간초과가 뜹니다.. 무슨 방법없을가요??

import collections


def bfs():
    direct = [[0, 1], [1, 0], [0, -1], [-1, 0]]

    q = collections.deque()
    q.append((0, 0, board[0][0]))
    max_size = 1

    while q:
        y, x, data = q.popleft() # 0 0 C / 0 1 CA / 1 1 CAD
        for dy, dx in direct:
            ny = y + dy
            nx = x + dx
            if ny < 0 or nx < 0 or ny >= r or nx >= c:
                continue
            if board[ny][nx] in data:
                continue
            else:
                q.append((ny, nx, data + board[ny][nx]))
                max_size = max(max_size, len(data)+1)
    print(max_size) # len("CAD")

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

bfs()

mason 7년 전 0

혹시 다른 문제들 푸셨을 때 다른 python 제출자 분들에 비해서 메모리가 비정상적으로 크거나 하지 않으신가요?

tkqlzz 7년 전 0

그게 어느날부터 python3으로 a+b같은 것만 제출해도 기본적으로 35004 kb가 나오더군요. 근데 다른분들도 다 그렇게 나오시구

다른문제 풀땐 딱히 문제없는거보면 메모리초과가 경우의수가 너무많아 생기는거 같습니다.

tkqlzz 7년 전 0

dfs로 메모리를 줄이고자 했더니 시간초과.. 이리저리 해메다 예제문제 몇번 돌리고 큐 상태를 보니까 위 코드가 중복되는걸 그냥 방지했더라구요

중복되는걸 기록하는 조건을 주어서 해결하였습니다.

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

문제

문제

출처

ICPC

#1987 python 메모리초과 어떻게 해야될지 모르겠습니다.

tkqlzz 7년 전 0

mason 7년 전 0

tkqlzz 7년 전 0

tkqlzz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말