글 읽기 - python(파이썬) 시간초과

gonigoni 1년 전 0

방금전 콘테스트 4번 문제 푸신분 있으신가요

pypy3로 해도 시간초과가 나오는데 접근방법이 틀린건지 궁금합니다.

마네킹에 대한 distance를 미리 계산해두고 BFS로 풀었습니다.

from collections import deque
import sys
input = sys.stdin.readline
N,M,K = map(int, input().split())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split()))) 


y = 0
x = 0
king = []
dist = [[sys.maxsize for _ in range(M)] for _ in range(N) ]
for i in range(N):
    for j in range(M):
        if graph[i][j] == 4:
            x, y = j, i
        elif graph[i][j] == 3:
            king.append([i,j])

for i in range(N):
    for j in range(M):
        for ki in king:
            dist[i][j] = min(dist[i][j], abs(ki[0]-i) + abs(ki[1]-j))
            
queue = deque([[y, x, 0]])
next_step = [[0,1],[1,0],[0,-1],[-1,0]]
while queue:
    y, x, step = queue.popleft()
    if dist[y][x] <= K and graph[y][x] != 4:
        continue
    elif graph[y][x] == 2:
        print(step)
        exit(0)
        
    graph[y][x] = 1
    for n in next_step:
        ny = y + n[0]
        nx = x + n[1]
        if ny < 0 or nx < 0 or ny >= N or nx >= M:
            continue
        elif graph[ny][nx] == 1:
            continue
        else:
            queue.append([ny, nx, step+1])
    
print(-1)

gonigoni 1년 전 2

마네킹에 대한 distance계산도 multisource bfs로 하니까 풀렸습니다.

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

문제

문제

출처

ICPC

python(파이썬) 시간초과

gonigoni 1년 전 0

gonigoni 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말