[백준/BOJ] platinum3 - 16930번 달리기 (Python)

▶16930 - 달리기

백준 로고

오랜만에 플래티넘 문제를 풀고 싶어서 쉬워 보이는 걸로 골랐다.
플래티넘3 문제지만 그렇게 어렵진 않았고, 플5 정도로 느껴졌다.

▶문제

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

728x90

▶풀이

일반적인 bfs로 경로를 탐색하는 문제와 거의 유사한 문제이다.

다만 한 번에 여러 칸을 이동할 수 있기에

반복문을 통해서 1~k만큼 이동한걸 모두 queue에 넣어주어야 한다.

 

그리고 visit가 0이 아니라고 해서 그냥 넘어가면 안 된다.

왜냐하면 이미 방문했지만 그 길을 따라 쭈욱 갈 수 있기 때문이다.

 

visit[nx][ny]가 visit[x][y] + 1일 경우에는 같은 횟수로 더 갈 수 있기에,

이미 방문한 노드지만 continue 해서 계속 연결해 주면 된다.

from collections import deque


def bfs():
    queue = deque()
    queue.append([x1 - 1, y1 - 1])

    while queue:
        x, y = queue.popleft()
        if x == x2 - 1 and y == y2 - 1:
            return visit[x][y]
        
        for i in range(4):
            for num in range(1, k + 1):
                nx = x + dx[i] * num
                ny = y + dy[i] * num
                
                if 0 <= nx < n and 0 <= ny < m and arr[nx][ny] == '.':
                    if visit[nx][ny] == 0:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append([nx, ny])
                    elif visit[nx][ny] == visit[x][y] + 1:
                        continue
                    else:
                        break
                else:
                    break
    
    return -1


n, m, k = map(int, input().split())
arr = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
visit = [[0 for _ in range(m)] for _ in range(n)]

for _ in range(n):
    arr.append(list(input().rstrip()))

x1, y1, x2, y2 = map(int, input().split())
print(bfs())