BOJ 16930. 달리기 (파이썬 Python)

Solved.ac 기준 플레티넘 2

달리기 

문제

진영이는 다이어트를 위해 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수까지 돌리면서 찰때마다 카운트 하는것. (BFS) 을 생각했었다.

그래서 그렇게 코드를 단순하게 짜보았지만, 5% 가고 틀렸습니다가 떳다. 그래서 뭐가 문제인지를 한참 고민했었지만..도저히 내 머리에선 나오지 않았다.

https://covenant.tistory.com/147

🏁 거침없는 코딩테스트 DFS BFS 문제 추천

이분의 풀이를 보고 해석하기 시작했다.

일단 K까지 돌린다는 생각 자체는 같았다. 하지만, 내가 말했던 돌림은 4방향을 다 돌면서 비효율적으로 돌리게 된거였고, 위 코드에서는 하나의 방향을 정했으면 그 방향이 될때까지 계속 가는 것이었다. 이래야지 시간복잡도를 봐도 훨씬 효율적이고, 직관적이기도 하다. 

while에 모든 오류 가능성을 다 때려박아서 만든 코드였다. 확실히 코드가 보기가 편했다. 그외에는 일반적인 BFS풀이였다.

(하지만 그걸 생각해 내는게 어렵다) (이래서 플래티넘 문제인가보다)

 

아 그리고 이 코드는 파이썬으로 돌릴 시 시간초과가 난다. PyPy로 돌려야지 통과 된다. 이 시간 줄이는 방법은 추후에 고민해보도록 하겠다.

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

dist = [[float('inf')]* (M) for _ in range(N)]
dx = [-1,0,1,0]
dy = [0,-1,0,1]
board = []
for i in range(N):
    text = list(input().rstrip())
    board.append(list(text))
x1,y1,x2,y2 = map(int,input().split())
q = deque()
c = 1
q.append((x1-1,y1-1))
dist[x1-1][y1-1] = 0

while q:
    x,y= q.popleft()
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        cnt = 1
        while cnt <= K and 0 <= nx < N and 0 <= ny < M and board[nx][ny] != '#' and dist[nx][ny] > dist[x][y]:
            if dist[nx][ny] == float('inf'):
                q.append((nx,ny))
                dist[nx][ny] = dist[x][y] + 1
            nx += dx[i]
            ny += dy[i]
            cnt += 1

if dist[x2-1][y2-1] == float('inf'):
    print(-1)
else:
    print(dist[x2-1][y2-1])