Baekjoon-16930-달리기
27 Sep 2022쉬운 BFS 이지만 시간초과때문에 Platinum 난이도를 얻었다.
O(MNK) 를 O(MN)으로 고쳐주는 break문을 넣어주는게 핵심 포인트
그리고 Python으로는 풀 수 없는 문제일지도? PyPy를 써야 시간제한에 걸리지 않는다. 그러나 PyPy는 메모리를 약 3배 더 잡아먹으니 주의하도록 하자. (삼성 SW 평가는 PyPy3로 돌려본다고 함)
ref: https://algorithmstudy-mju.tistory.com/137
import sys
input = sys.stdin.readline
from collections import deque
N,M,K = map(int, input().split())
# build map
maps = [[1 for _ in range(M)] for _ in range(N)]
visited = [[-1 for _ in range(M)] for _ in range(N)]
for n in range(N):
row = input().strip()
for m in range(M):
if row[m] == '#':
maps[n][m] = 0
x1,y1,x2,y2 = map(int, input().split())
x1,y1,x2,y2 = map(lambda x: x-1, [x1,y1,x2,y2])
queue = deque([[x1,y1]])
visited[x1][y1] = 0
while queue:
x,y = queue.popleft()
if x == x2 and y == y2:
print(visited[x][y])
exit()
for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
for k in range(1, K+1):
x3, y3 = x+dx*k, y+dy*k
if (0 <= x3 < N) and (0 <= y3 < M):
if maps[x3][y3] == 0:
break
elif visited[x3][y3] == -1:
visited[x3][y3] = visited[x][y] + 1
queue.append([x3,y3])
elif visited[x3][y3] <= visited[x][y]: # O(NMK) -> O(NM)
break
else:
break
print(visited[x2][y2])