[백준] 1600 - 말이 되고픈 원숭이 (Python)

https://www.acmicpc.net/problem/1600

 

3차원 BFS 문제이다.

dist[i][j][k] 를 (i, j) 위치에 있을 때 현재 남은 말 이동 횟수가 k 인 경우 그때까지 최소 이동거리라고 정의한 뒤,

 

일반 이동을 하는 경우

dist[next_i][next_j][now_k] = min(dist[next_i][next_j][now_k], dist[now_i][now_j][now_k] + 1)

 

말로 이동하는 경우 k 를 소모하므로

dist[next_i][next_j][now_k-1] = min(dist[next_i][next_j][now_k-1], dist[now_i][now_j][now_k] + 1)

 

이렇게 식을 세운뒤, dist 배열은 초기값을 INF 값 (파이썬은 보통 9876543210) 으로 초기화 하고, (0, 0, k) 에서부터 BFS를 돌면서 채우면 된다.

 

from collections import deque
import sys
input = sys.stdin.readline
INF = 9876543210
di = [0, 0, -1, 1]
dj = [-1, 1, 0, 0]

di_horse = [-1, -2, -2, -1, 1, 2, 2, 1]
dj_horse = [-2, -1, 1, 2, -2, -1, 1, 2]

k = int(input())
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
dist = [[[INF for _ in range(k + 1)] for _ in range(m)] for _ in range(n)]
visit = [[[False for _ in range(k+1)] for _ in range(m)] for _ in range(n)]

dist[0][0][k] = 0
d = deque()
d.append((0, 0, k))
visit[0][0][k] = True

while d:
    now_i, now_j, now_k = d.popleft()
    # print(now_i, now_j, now_k)

    # check adjacent pos
    for l in range(4):
        next_i, next_j = now_i + di[l], now_j + dj[l]
        if 0 <= next_i < n and 0 <= next_j < m:
            if graph[next_i][next_j] == 0 and not visit[next_i][next_j][now_k]:
                dist[next_i][next_j][now_k] = min(dist[next_i][next_j][now_k], dist[now_i][now_j][now_k] + 1)
                visit[next_i][next_j][now_k] = True
                d.append((next_i, next_j, now_k))

    # check horse:
    if now_k:
        for l in range(8):
            next_i, next_j = now_i + di_horse[l], now_j + dj_horse[l]
            if 0 <= next_i < n and 0 <= next_j < m:
                if graph[next_i][next_j] == 0 and not visit[next_i][next_j][now_k-1]:
                    dist[next_i][next_j][now_k-1] = min(dist[next_i][next_j][now_k-1], dist[now_i][now_j][now_k] + 1)
                    visit[next_i][next_j][now_k-1] = True
                    d.append((next_i, next_j, now_k-1))

answer = min(dist[n-1][m-1])
print(-1 if answer == INF else answer)