[백준 1600번 말이 되고픈 원숭이] 문제풀이

import sys
from collections import deque

input = sys.stdin.readline

'''
평범한 BFS에서 약간의 응용이 들어감
horse의 움직임과 monkey의 움직임을 저장
함수에 들어가기 전 0으로 초기화된 그래프 생성
visited, queue 초기화 
    여기서 queue에 들어갈 인자는 x,y 뿐만 아니라 말처럼 움직일 수 있는 횟수, 지금까지 움직인 횟수까지
    curY, curX, horseCount, curMove  = queue에 들어있는 값을 빼온다
    만약 horseCount가 유효하면 > 0
        horse 이동방식으로 graph에 족적 남기고 queue에 위치 더하기 - 함수로 빼놓으면 가독성 올라갈듯
        horseCount -= 1
    아니면
        원숭

탐색이 끝나면 graph[h-1][w-1] 출력
        
global
    원숭, 말 이동 패턴
    0으로 초기화된 graph
    입력받은 graph
local
    각 queue에 들어갈 인자들
    방문을 처리할 set 하나

문제발생!
말을 아껴놨다가 장애물을 넘어갈 수 있는 위치에서만 사용할 수 있게 구현해야함
한차원 높혀서 모든 경우의 수를 판단해야할듯
visited에 horseCount를 포함해 원숭이 -> 말 -> 원숭이 이런 연산도 가능하게 바꿔야함
'''
horseDY = [-2, -1, -2, -1, 2, 1, 2, 1]
horseDX = [-1, -2, 1, 2, -1, -2, 1, 2]

monkeyDY = [-1, 1, 0, 0]
monkeyDX = [0, 0, -1, 1]

K = int(input())

W, H = map(int, input().split())


def likeMonkey(y, x, horseCount, queue, visited, moves):
    for i in range(4):
        newY, newX = y + monkeyDY[i], x + monkeyDX[i]
        if 0 <= newY < H and 0 <= newX < W and graph[newY][newX] == 0 and (newY, newX, horseCount) not in visited:
            queue.append((newY, newX, horseCount, moves + 1))
            visited.add((newY, newX, horseCount))



def likeHorse(y, x, horseCount, queue, visited, moves):
    for i in range(8):
        newY, newX = y + horseDY[i], x + horseDX[i]
        if 0 <= newY < H and 0 <= newX < W and graph[newY][newX] == 0 and (newY, newX, horseCount -1) not in visited:
            queue.append((newY, newX, horseCount - 1, moves + 1))
            visited.add((newY, newX, horseCount - 1))


def bfs():
    # 여기서 queue에 들어갈 인자는 x,y 뿐만 아니라 말처럼 움직일 수 있는 횟수, 지금까지 움직인 횟수까지
    queue = deque([(0, 0, K, 0)])
    visited = {(0, 0, K)}
    while queue:
        curY, curX, horseCount, moves = queue.popleft()

        if curY == H - 1 and curX == W - 1:
            return moves

        likeMonkey(curY, curX, horseCount, queue, visited, moves)
        if horseCount > 0:
            likeHorse(curY, curX, horseCount, queue, visited, moves)
    return -1


graph = []

for _ in range(H):
    graph.append(list(map(int, input().split())))

print(bfs())