글 읽기 - 16933 파이썬 벽부수고이동하기3 질문

alftjd1 3년 전 0

시간초과가 발생해서 이곳 저곳을 돌아다니며 코드 로직을 가져와 다시써보기도하고

최소한으로 코드도 줄여보기도 하고 그랬는데 모두 17%에서 시간초과가 발생하네요.

솔직히 시간초과 해결해도 메모리초과가 받아질것 같긴한데.

그레도 시간초과는 해결해보고 싶기에 질문을 올려봅니다.

from collections import deque
from sys import stdin
input = stdin.readline

n, m, k = map(int,input().split())
world = [list(map(int,input().strip())) for _ in range(n)]
graph = [[[[0 for _ in range(m)] for _ in range(n)] for _ in range(k+1)] for _ in range(2)]
graph[0][k][0][0] = 1 # 낮/밤 상태, 뚫을 수 있는 벽의 갯수, y좌표, x좌표
temp = deque([(0,k,0,0)]) # 위와 같음

def main():
    while temp:
        d, b, i, j = temp.popleft()

        if i == n-1 and j == m-1:
            return graph[d][b][i][j]

        if not graph[~d][b][i][j]:
            graph[~d][b][i][j] = graph[d][b][i][j] + 1
            temp.append((~d,b,i,j))

        for x, y in (1,0),(0,1),(~0,0),(0,~0):
            nx, ny = x + i, y + j

            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue

            if not d and b and not graph[~d][b-1][nx][ny] and world[nx][ny]:
                graph[~d][b-1][nx][ny] = graph[d][b][i][j] + 1
                temp.append((~d,b-1,nx,ny))

            if not graph[~d][b][nx][ny] and not world[nx][ny]:
                graph[~d][b][nx][ny] = graph[d][b][i][j] + 1
                temp.append((~d,b,nx,ny))

    return -1

print(main())

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

문제

문제

출처

ICPC

16933 파이썬 벽부수고이동하기3 질문

alftjd1 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말