[백준] 1600번 - 말이 되고픈 원숭이 (파이썬)

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

 

# 말이 되고픈 원숭이
from collections import deque
import sys
input = sys.stdin.readline
monkey_dx = [0, 1, 0, -1]
monkey_dy = [1, 0, -1, 0]
horse_dx = [-2, -1, 1, 2, 2, 1, -1, -2]
horse_dy = [1, 2, 2, 1, -1, -2, -2, -1]


def bfs(n):
    q = deque()
    q.append((0, 0, n))
    count = [[[0] * (n + 1) for _ in range(M)] for _ in range(N)]
    while q:
        x, y, K = q.popleft()
        if x == N-1 and y == M-1:
            return count[x][y][K]
        if K > 0:
            for k in range(8):
                nx = x + horse_dx[k]
                ny = y + horse_dy[k]
                if 0 <= nx < N and 0 <= ny < M:
                    if arr[nx][ny] != 1 and count[nx][ny][K-1] == 0:
                        count[nx][ny][K-1] = count[x][y][K] + 1
                        q.append((nx, ny, K-1))
        for k in range(4):
            nx = x + monkey_dx[k]
            ny = y + monkey_dy[k]
            if 0 <= nx < N and 0 <= ny < M:
                if arr[nx][ny] != 1 and count[nx][ny][K] == 0:
                    count[nx][ny][K] = count[x][y][K] + 1
                    q.append((nx, ny, K))
    return -1


K = int(input())
M, N = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
result = bfs(K)
print(result)

 

BFS

1. 3차원 count 리스트를 정의한다 (count[x][y][남은 말처럼 이동가능한 횟수])

2. q가 빌 때 까지

  - 말처럼 이동 가능한 횟수(K)가 0보다 크면 말처럼 이동

     - 해당위치가 장애물이 아니고, 해당 방법으로 이동한 적이 없으면(count[nx][ny][K]==0)

     - K-1한 위치에 이전 count +1

  - 원숭이처럼 이동

  - 목표위치에 도착하면 return

3. 출력

 

2차원 배열로 했을 때, 원숭이처럼 이동과 말처럼 이동, 두가지가 겹치는 부분을 처리해줄 방법이 없었다.

고민하다가 3차원 배열로 해결했다.