[ BOJ ] 16930 : 달리기 ( PLATINUM 3 ) / Python

문제

진영이는 다이어트를 위해 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을 출력한다.

풀이 과정

BFS를 이용하여 탐색을 하되, 방문 처리에 이동 시간을 기록하여 만약 이전 이동 시간에 이 위치를 지났을 경우 탈출한다.

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

n, m, k = map(int, input().split())
maps = [list(input()) for _ in range(n)]
y1, x1, y2, x2 = map(int, input().split())

q = deque()

visit = [[-1 for j in range(m)] for i in range(n)]
visit[y1-1][x1-1] = 0

q.append((y1-1, x1-1))

# Left, Up, Right, Down
row = [0, -1, 0, 1]
col = [-1, 0, 1, 0]

result = -1

time = 1
done = 0
while q:
    y, x = q.popleft()
    
    if y == y2-1 and x == x2-1:
        result = visit[y][x]
        done = 1
        break

    for d in range(4):
        for cnt in range(1, k+1):
            ny = y + (row[d] * cnt)
            nx = x + (col[d] * cnt)
            
            if not (0 <= ny < n) or not (0 <= nx < m) or maps[ny][nx] == '#' or (visit[ny][nx] != -1 and visit[ny][nx] < visit[y][x] + 1): break
            if visit[ny][nx] == -1:
                visit[ny][nx] = visit[y][x] + 1
                q.append((ny, nx))

    if done == 1: break
    time += 1
    
print(result)

이전에 이동했던 시간보다 더 빠르게 이동할 수 있는 루트를 찾을 수 있는 솔루션이라 재미있는 문제였다.