글 읽기 - 파이썬 시간초과, 메모리초과

bsyzch 3년 전 0

bfs 방식으로 구현하였는데 메모리 초과가 왜 뜰까요?

visited 를 3차원으로 구현하는건 다른분들도 이런 식으로 하셔bfs 방식으로 구현하였는데 메모리 초과가 왜 뜰까요?

visited 를 3차원으로 구현하는건 다른분들도 이런 식으로 하셔서 문제 없는것 같고

제 생각엔 그나마 의심가는 부분은 26~36 line에서 상하좌우 움직임 체크할 때 뭔가 문제가 있나? 싶긴한데 잘 모르겠네요

python이랑 pypy 제출시 각각 시간초과, 메모리 초과 결과가 뜹니다.

이런 경우 쓸데 없는 선언을 통해 뭔가 낭비시킨 것 같은데 잘 모르겠네요..

from collections import deque

dx, dy = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1] #시계방향
dx2, dy2 = [-1, 1, 0, 0], [0, 0, -1, 1] #상하좌우

k = int(input())
m, n = map(int, input().split())  # m이 가로 n이 세로
arr = []
visited = [[[0] * m for _ in range(n)] for _ in range(k)]
visited[0][0][0] = 1

for i in range(n): #맵 정보 입력
    arr.append(list(map(int, input().split())))

q = deque()
q.append((0, 0, 0, 0)) # x좌표, y좌표, 이동비용, 말이 움직인 횟수


def bfs():  # x -> row | y -> col
    while q:
        x, y, count, action = q.popleft() # x, y=좌표 정보 | count=움직인 횟수 | action=말의 움직임을 쓴 횟수
        if x == n - 1 and y == m - 1: #목적지 도착
            print(count)
            return

        for i in range(4):      #상하좌우 이동
            nx = x + dx2[i]
            ny = y + dy2[i]
            if action >= k:     #말의 움직임을 다 쓴 경우 visited에 최대 사용가능한 말의 움직임 k로 저장한다.
                if 0 <= nx < n and 0 <= ny < m and visited[k][nx][ny] == 0 and arr[nx][ny] == 0:
                    visited[k][nx][ny] = 1
                    q.append((nx, ny, count + 1, action))
            else:               #말의 움직임을 다 안 쓴 경우 현재 사용한 말의 움직임을 visited에 저장
                if 0 <= nx < n and 0 <= ny < m and visited[action][nx][ny] == 0 and arr[nx][ny] == 0:
                    visited[action][nx][ny] = 1
                    q.append((nx, ny, count + 1, action))

        if action < k:          #말의 움직임 이동 (시계방향)
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0 <= nx < n and 0 <= ny < m and visited[action][nx][ny] == 0 and arr[nx][ny] == 0:
                    visited[action + 1][nx][ny] = 1
                    q.append((nx, ny, count + 1, action + 1))
    return -1 #큐를 다 돌렸는데 목적지 도착해서 return 되지 않은 경우 -1 return


if bfs() == -1:  # 말의 이동
    print(-1)

djm03178 3년 전 2

43, 44번째 줄에서 action + 1을 큐에 넣고 있으므로 조건 검사도 visited[action + 1][nx][ny] == 0으로 해야 합니다.

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

문제

문제

출처

ICPC

파이썬 시간초과, 메모리초과

bsyzch 3년 전 0

djm03178 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말