📩 출처
문제
진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다.
매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다.
시작점 (x1, y1)과 도착점 (x2, y2)가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간을 구해보자.
입력
첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다.
둘째 줄부터 N개의 줄에는 체육관의 상태가 주어진다. 체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 '.', 벽은 '#'으로 주어진다.
마지막 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 두 칸은 서로 다른 칸이고, 항상 빈 칸이다.
출력
(x1, y1)에서 (x2, y2)로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.
👉 생각
- 너비 우선 탐색을 하면서 도착점을 찾아간다.
- 기존의 한 번에 한칵씩 이동하던 것과는 달리 k번까지 동일한 초 안에 큐에 넣을 수 있다.
- 그런데 탐색하는 방향에 따라서, 큐에 넣어주어야하는데, 기존에 방문한 적이 있는 좌표를 다시 방문하는 경우가 있다. 따라서 방문한적이 있고, 그 지점까지 방문한 시간이, 현재 시간보다 크다면, 방문하지 않고 그 다음으로 넘어가는 식으로 분기 처리를 진행했다.
from collections import deque
import sys
def bfs():
q = deque([(x1-1, y1-1)])
visited = [[0] * m for _ in range(n)]
while q:
x, y = q.popleft()
if x == x2-1 and y == y2-1:
return visited[x][y]
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
for i in range(1, k+1):
nx, ny = x + dx * i, y + dy * i
if nx < 0 or nx >= n or ny <0 or ny >= m or arr[nx][ny] == '#':
break
if not visited[nx][ny]:
q.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
elif visited[nx][ny] > visited[x][y]:
continue
else:
break
return -1
input = sys.stdin.readline
n, m, k = map(int, input().split())
arr = [list(input().rstrip()) for _ in range(n)]
x1, y1, x2, y2 = map(int, input().split())
print(bfs())