[BaekJoon] 백준 1600번 : 말이 되고픈 원숭이

1600번 : 말이 되고픈 원숭이

방문 여부를 해당 좌표를 왔다고만 해서 방문했다고 하지말고 말을 몇 번 타고 왔는지 여부를 함께 저장하면 된다.

예를들어 (2, 2) 좌표를 말을 한 번 타고 왔을 때 이동 횟수, 두 번 타고 왔을 때 … 저장을 하면 모든 경우를 따질 수 있다.

큐에는 상, 하, 좌, 우 와 말을 타고 이동하는 경우 8 가지를 모두 조건에 맞으면 넣어준다.

---

import sys
from collections import deque


def solution():
    visit = dict()
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    horse_dirs = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, -1], [2, 1], [-1, -2], [1, -2]]
    queue = deque([(0, 0, 0, 0)])
    visit[(0, 0, 0)] = True

    while queue:
        now_i, now_j, now_dist, now_horse_cnt = queue.popleft()
        if now_i == N - 1 and now_j == M - 1:
            return now_dist

        for value in horse_dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < M and (visit_i, visit_j, now_horse_cnt + 1) not in visit:
                if field[visit_i][visit_j] != 1:
                    if now_horse_cnt < K:
                        visit[(visit_i, visit_j, now_horse_cnt + 1)] = True
                        queue.append((visit_i, visit_j, now_dist + 1, now_horse_cnt + 1))

        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < M and (visit_i, visit_j, now_horse_cnt) not in visit:
                if field[visit_i][visit_j] != 1:
                    visit[(visit_i, visit_j, now_horse_cnt)] = True
                    queue.append((visit_i, visit_j, now_dist + 1, now_horse_cnt))

    return -1


if __name__ == "__main__":
    K = int(input())
    M, N = map(int, input().split())
    field = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(N)]

    print(solution())