BOJ :: [1600] 말이 되고픈 원숭이

문제

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

1600번: 말이 되고픈 원숭이

 

문제 요약

말이 되고픈 원숭이 문제는 주어진 원숭이의 움직임으로 판(2차원 배열)의 오른쪽 위(0, 0)에서 왼쪽 아래(h-1, w-1)까지의 최단거리를 구하는 문제이다. 주어진 판에서 1은 벽을 의미하며 0은 평지를 의미한다. 원숭이는 벽을 말은 체스의 '나이트'와 같이 움직일 수 있다(말은 장애물을 뛰어넘을 수 있다).

 

말의 움직임(체스의 나이트)

원숭이는 말과 같이 k번 움직일 수 있으며, 말처럼 k번 움직인 후에는 원숭이가 있는 위치에서 위, 아래, 좌, 우로만 움직일 수 있다. 인접한 방향으로 움직이는 것과 말과 같이 움직이는 것 모두 한 번의 이동으로 간주한다.

말처럼 이동할 수 있는 횟수 k와 w, h, 판의 정보가 주어졌을때 (0,0)에서 (h, w)까지의 최단거리를 구해야 한다.

 

풀이

이 문제를 보고 평범한 BFS문제라고 생각했다. visit배열을 판과 같은 사이즈로 만들어 maxsize로 초기화시켜주고, BFS로 탐색하면서 visit 배열에 저장된 횟수보다 현재까지의 움직임이 더 작을 때만 값을 업데이트하면 최종적으로 (h-1, w-1) 위치에는 최소 움직임 횟수만 남아 정답을 구할 수 있다고 생각했다.

위와 같은 방법으로 문제를 풀 경우 말의 움직임으로 한번 방문했던 좌표를 계속해서 다시 방문하면서 시간초과가 발생한다. 따라서 시간 초과를 해결하기 위해 말의 움직임 능력의 사용 횟수에 따른 최솟값을 저장할 수 있도록 3차원 배열을 사용해서 문제를 해결했다.

visit [x][y][k-i] = value : visit [x][y]까지 말의 움직임을 i번 사용하여 오는데 value만큼 걸렸다는 의미이다.

 

현재 위치를 기준으로 상, 하, 좌, 우, 말과 같이 움직일 때 아래와 같이 dx, dy 배열을 만들어두면 편하게 구현할 수 있다.

 

- 말과 같이 이동할 경우

dx = [2, 2, -2, -2, 1, 1, -1, -1]

dy = [1, -1, 1, -1, 2, -2, 2, -2]

말 움직임

- 인접한 곳으로 이동할 경우

dx = [0, 0, 1, -1]

dy = [1, -1, 0, 0]

원숭이 움직임

코드

import sys
from collections import deque
from typing import Sized

def horse(x, y, cnt):
    dx = [2, 2, -2, -2, 1, 1, -1, -1]
    dy = [1, -1, 1, -1, 2, -2, 2, -2]

    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= 0 and nx < h and ny >= 0 and ny < w:
            if arr[nx][ny] == 0 and visit[nx][ny][cnt-1] > visit[x][y][cnt] + 1:
                q.append((nx, ny, cnt-1))
                visit[nx][ny][cnt-1] = visit[x][y][cnt] + 1
    return

def move(x, y, cnt):
    dx = [0, 0, 1, -1]
    dy = [-1, 1, 0, 0]

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx >= 0 and nx < h and ny >= 0 and ny < w:
            if arr[nx][ny] == 0 and visit[nx][ny][cnt] > visit[x][y][cnt] + 1:
                q.append((nx, ny, cnt))
                visit[nx][ny][cnt] = visit[x][y][cnt] + 1

    return

input = sys.stdin.readline

k = int(input())
w, h = map(int, input().split())

arr = []
visit = [[[sys.maxsize for i in range(k+1)] for j in range(w)] for z in range(h)]

for i in range(h):
    arr.append(list(map(int, input().split())))

q = deque()

q.append((0, 0, k))

visit[0][0][k] = 0

if w == 1 and h == 1 and arr[0][0] == 1:
    print(-1)
    sys.exit()

while q:
    x, y, cnt = q.popleft()
    
    if cnt > 0:
        horse(x, y, cnt)
        
    move(x, y, cnt)

result = min(visit[h-1][w-1])

if result == sys.maxsize:
    result = -1

print(result)

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다 . 질문도 환영합니다! :)