백준 1600. 말이 되고픈 원숭이

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

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

k = int(input())  # 말처럼 이동할 수 있는 횟수
w, h = map(int, input().split())  # 가로, 세로 크기
arr = [list(map(int, input().split())) for _ in range(h)]

# 4방향(원숭이 이동)
monkey_moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# 8방향(말 이동)
horse_moves = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]

# 방문 배열: (x, y, 남은 말 이동 횟수)
visited = [[[False] * (k + 1) for _ in range(w)] for _ in range(h)]

def bfs():
    queue = deque([(0, 0, 0, k)])  # (x, y, 이동 횟수, 남은 말 이동 횟수)
    visited[0][0][k] = True

    while queue:
        x, y, steps, horse_left = queue.popleft()

        # 도착지점에 도달하면 이동 횟수 반환
        if x == h - 1 and y == w - 1:
            return steps

        # 원숭이 이동
        for dx, dy in monkey_moves:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny][horse_left] and arr[nx][ny] == 0:
                visited[nx][ny][horse_left] = True
                queue.append((nx, ny, steps + 1, horse_left))

        # 말 이동 (말처럼 이동할 기회가 남아 있는 경우)
        if horse_left > 0:
            for dx, dy in horse_moves:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w and not visited[nx][ny][horse_left - 1] and arr[nx][ny] == 0:
                    visited[nx][ny][horse_left - 1] = True
                    queue.append((nx, ny, steps + 1, horse_left - 1))

    # 도달할 수 없는 경우
    return -1

print(bfs())

BFS의 특징: 최소 비용 경로를 보장

이 문제에서 사용하는 **BFS(너비 우선 탐색)**는, 한 단계씩 탐색을 진행하기 때문에 가장 먼저 도달하는 경로가 최소 이동 경로임을 보장합니다.

즉, 어떤 위치 (x, y)에 도달했을 때, 해당 위치를 BFS 탐색 순서로 가장 먼저 방문한 경우가 그 위치로 가는 최단 거리입니다.