글 읽기 - 파이썬 시간 초과...

jinhot 4년 전 0

파이썬으로 풀어보려고 하는데,

시간 초과를 극복할 수가 없습니다.. ㅜㅜ

심지어 구글에서 C++로 푼 사람 로직대로 그대로 바꿔봤는데도 시간 초과가 뜨네요..

제가 잘못 바꾼건지...

혹시 괜찮으시면 보시고 고견 부탁드립니다..

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())

board = []

for i in range(N):
    board.append(list(map(int, list(input().strip()))))

visited = [[[False for k in range(K + 1)] for j in range(M)] for i in range(N)]
visiting = [(0, 0, K)]
visited[0][0][0] = True

available_pos = [[-1, 0], [1, 0], [0, -1], [0, 1]]

not_found = True
count = 0
while not_found and visiting and count < N*M:
    count += 1
    #visiting = list(set(visiting))
    len_visit = len(visiting)
    for i in range(len_visit):
        now_pos = visiting.pop(0)

        # 종료 조건
        if (now_pos[0], now_pos[1]) == (N - 1, M - 1):
            not_found = False
            break

        for added in available_pos:
            new_pos_i = now_pos[0] + added[0]
            new_pos_j = now_pos[1] + added[1]
            new_k = now_pos[2]
            if not (0 <= new_pos_i < N and 0 <= new_pos_j < M):
                continue
            
            if board[new_pos_i][new_pos_j] == 1:
                new_k -= 1
                if new_k < 0:
                    continue
            
            if visited[new_pos_i][new_pos_j][new_k] == False:
                visited[new_pos_i][new_pos_j][new_k] = True
                visiting.append((new_pos_i, new_pos_j, new_k))  

if not not_found:
    print(count)
else:
    print(-1)