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

문제

1600번: 말이 되고픈 원숭이

 

문제 풀이

 문제에서 원숭이는 K번 동안, 나이트의 이동과 같이 8 방향으로 이동할 수 있으며 그 이후에는 상, 하, 좌, 우 한칸씩 움직이게 된다. 이때, 최소의 횟수로 우측 하단 아래의 좌표로 도착하는 경우를 반환하는 문제이다. 이는 벽을 K번 부술 수 있는 벽 부수고 이동하기 2와 유사한 로직으로 풀면 된다.

 

• BFS를 통해, K가 있다면 말, 원숭이 처럼 이동가능한 모든 경우의 수를 큐에 추가한다.
• K가 없다면, 원숭이 처럼 이동가능한 모든 경우의 수를 큐에 추가한다.
• 말 처럼 이동한 횟수에 따라 방문 경로를 구분하여야 한다.
  • 이를 위해 `visited`를 x, y, 말처럼 이동한 횟수로 하여 3차원 배열로 만든다.
  • `visited`는 단순히 방문 여부를 확인하는 것이 아닌, 기존의 경로에서 해당 경로로 방문하는데 걸린 시간을 누적한다.

 

코드

from sys import stdin
from collections import deque


def visitable(x, y, next_k):
    return 0 <= x < h and 0 <= y < w and not visited[x][y][next_k] and not graph[x][y]


def bfs(start):
    q = deque([start])

    horse_dirs = ((-1, 2), (1, 2), (2, 1), (2, - 1),
                  (1, -2), (-1, -2), (-2, -1), (-2, 1))
    monkey_dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))

    while q:
        x, y, cur_k = q.popleft()

        if (x, y) == (h - 1, w - 1):
            return visited[x][y][cur_k]

        dirs = monkey_dirs + horse_dirs if cur_k > 0 else monkey_dirs

        for idx, delta in enumerate(dirs):
            next_x, next_y = x + delta[0], y + delta[1]
            next_k = cur_k - 1 if idx > 3 else cur_k

            if visitable(next_x, next_y, next_k):
                q.append((next_x, next_y, next_k))
                visited[next_x][next_y][next_k] = visited[x][y][cur_k] + 1
    return -1


if __name__ == '__main__':
    k = int(stdin.readline())
    w, h = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(h)]
    visited = [[[0] * (k + 1) for _ in range(w)]for _ in range(h)]
    print(bfs((0, 0, k)))

 3차원 배열로 `visited`를 만들어야 겠다는 생각을 바로 떠올리지 못하여, 이리저리 헤매서 시간을 좀 썻다.😅