[백준] 1600 말이 되고픈 원숭이 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1600
• 🔑 BFS
  • 중요한 점
    • 갔던 곳이라도 더 빠르게 갈 수 있다면 가야 한다.
  • 원숭이 이동, 말 이동을 따로 만든다.
  • 큐에 x, y, 이동 횟수, 말 능력 사용 횟수를 넣는다. 초기 상태 = [0, 0, 0, 0]
  • 원숭이 이동은 항상 진행한다.
    • 조건은 범위 체크, 방문 체크, 말 능력 사용 횟수 체크
  • 말처럼 이동은 능력 사용 횟수가 남아 있을 때만 진행한다.
    • 조건은 범위 체크, 방문 체크, 말 능력 사용 횟수 체크

 

 

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

k = int(input())
w, h = map(int, input().split())
MAP = [list(map(int, input().split())) for _ in range(h)]

def bfs():
    visit = [[-1] * w for _ in range(h)]
    visit[0][0] = 0
    q = deque([[0, 0, 0, 0]])               # x, y, 이동 횟수, 말 능력 사용 횟수
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]   # 기본 이동
    hdx, hdy = [-2, -1, -2, -1, 2, 1, 2, 1], [1, 2, -1, -2, 1, 2, -1, -2]   # 능력 이동

    while q:
        x, y, cnt, skill = q.popleft()

        if x == h-1 and y == w-1:       # 도착하면 이동 횟수 리턴
            return cnt

        for i in range(4):              # 기본 이동
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < h and 0 <= ny < w and MAP[nx][ny] == 0:	# 범위 체크
                if visit[nx][ny] == -1 or visit[nx][ny] > skill:    # 안 갔거나, 더 적은 능력을 사용해서 갈 수 있으면
                    visit[nx][ny] = skill
                    q.append([nx, ny, cnt+1, skill])

        if skill < k:                   # 능력 사용 횟수가 남았으면
            for i in range(8):          # 능력 이동
                nx, ny = x + hdx[i], y + hdy[i]

                if 0 <= nx < h and 0 <= ny < w and MAP[nx][ny] == 0:
                    if visit[nx][ny] == -1 or visit[nx][ny] > skill + 1:    # 안 갔거나, 더 적은 능력을 사용해서 갈 수 있으면
                        visit[nx][ny] = skill + 1
                        q.append([nx, ny, cnt+1, skill+1])

    return -1

print(bfs())