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

문제 설명

 

입출력 예제

 

---

풀이 코드

이 문제는 2차원 배열이 아닌 3차원 배열 방식으로 풀어야 한다.

내가 3차원 배열로 표현한 방식은 visited[행][열][말처럼 움직일 수 있는 남은수(K)] 이다.

최소한의 동작으로 도착지점에 도착하기 위해서는 k번 말 처럼 움직인 다음 원숭이처럼 움직여야 최소한의 동작으로 도착 가능하다.

 

정답 코드

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

K = int(input())
W, H = map(int, input().split()) # 열, 행
board = [list(map(int, input().split())) for _ in range(H)]

# 말처럼 이동하는 경우
dx_knight = [-2, -1, 1, 2, 2, 1, -1, -2]
dy_knight = [1, 2, 2, 1, -1, -2, -2, -1]

# 원숭이 처럼 상하좌우로 이동하는 경우
dx_monkey = [0, 0, -1, 1]
dy_monkey = [1, -1, 0, 0]

def bfs():
    visited = [[[False] * (K+1) for _ in range(W)] for _ in range(H)]
    visited[0][0][K] = True
    queue = deque([(0, 0, K, 0)])

    while queue:
        x, y, k, move = queue.popleft()

        # 목표 지점 도달
        if x == H-1 and y == W-1:
            return move

        # 말처럼 이동하는 경우 - k(남은 움직일 수 있는 이동 횟수)가 1 이상인지 확인
        if k:
            for i in range(8):
                nx = x + dx_knight[i]
                ny = y + dy_knight[i]

                if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k-1] and board[nx][ny] != 1:
                    visited[nx][ny][k-1] = True
                    queue.append((nx, ny, k-1, move+1)) # 말처럼 움직인 횟수 1 차감, 이동 횟수 1 증감

        # 원숭이 처럼 상하좌우로 이동하는 경우
        for i in range(4):
            nx = x + dx_monkey[i]
            ny = y + dy_monkey[i]

            if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k] and board[nx][ny] != 1:
                visited[nx][ny][k] = True
                queue.append((nx, ny, k, move+1))
    return -1

print(bfs())

 

추가 설명

• 3차원 배열 초기화

visited 3차원 배열을 초기화 할 때 다음과 같이 했는데

visited = [[[False] * (K+1) for _ in range(W)] for _ in range(H)]

여기서 K+1을 한 이유는 원숭이가 말처럼 움직일 수 있는 기회가 K번 주어지기 때문에, 원숭이가 0번에서 K번까지 말처럼 움직일 수 있는 상황을 모두 기록하기 위함이다.

말처럼 움직이지 않았을 경우를 포함하기 때문에, 세 번째 차원의 크기를 K+1로 설정해야 원숭이가 0번부터 K번까지 말처럼 움직였을 때의 상태를 모두 저장할 수 있다.

 

 

• 말 처럼 이동하는 경우의 조건문

if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k-1] and board[nx][ny] != 1:
    visited[nx][ny][k-1] = True
    queue.append((nx, ny, k-1, move+1)) # 말처럼 움직인 횟수 1 차감, 이동 횟수 1 증감

여기서 왜 not visited[nx][ny][k]가 아닌 not visited[nx][ny][k-1]을 방문체크하는 건지 이해하기가 어려웠었다.

이 이유는 말처럼 이동하는 경우를 처리하기 때문이다. 

원숭이는 상하좌우로 이동하거나 말처럼 이동할 수 있고, 말처럼 이동할때마다 남은 이동 횟수 k를 하나씩 줄여야 합니다. 따라서 원숭이가 말처럼 움직일 때 다음 좌표를 (nx, ny, k-1)로 확인하고 방문 체크하는 것이다.