[boj] 1600_말이 되고픈 원숭이_python

문제링크

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

1600번: 말이 되고픈 원숭이

---

문제설명

문제

k번은 체스의 말처럼 움직일 수 있고

나머지는 상하좌우로만 움직일 수 있을 때

원숭이가 최소한의 동작으로 시작 -> 도착지점까지 갈 수 있는 최소 경우

 

입력

K : 말처럼 움직일 수 있는 수

W H : 가로, 세로 길이

W*H : 0일 때 갈 수 있는 곳, 1일 때 장애물로 인해 갈 수 없는 곳

출력

원숭이의 동작수의 최솟값 ( 도착할 수 없을 시 -1 출력 )

---

문제풀이

기본 발상

visited[ 미래의 좌표에서의 이동거리 ] = visited[ 현재의 좌표에서의 이동거리  ] + 1

미래의 좌표 : [Y][X]

현재의 좌표 : [y][x]

Case1. 말처럼 움직이는 경우

말처럼 움직인 횟수를 visited 배열 마지막 차원에 넣어줌

visited[Y][X][말처럼 움직인 횟수 + 1] = visited[y][x][말처럼 움직인 횟수] + 1

 

Case2. 원숭이처럼 움직이는 경우

말처럼 움직이지 않은 경우엔 "말처럼 움직인 횟수"가 늘어나지 않고 이동거리만 추가된다.

visited[Y][X][말처럼 움직인 횟수] = visited[y][x][말처럼 움직인 횟수] + 1

 

# 풀이시간 5h
# 시간 복잡도 : O(HWK) # O(8HWK + 4HW) # 말처럼 움직이는 경우 + 원숭이처럼 움직이는 경우
# 공간 복잡도 : O(HWK) # visited

import sys
from collections import deque
input = sys.stdin.readline
horse = [[2,1], [2, -1], [-2, 1], [-2, -1], [1,2], [1,-2], [-1, 2], [-1, -2] ]
monkey = [[0,1], [0, -1], [1, 0], [-1, 0]]
k = int(input())
W, H  = map(int, input().split())
zoo = [list(map(int, input().split())) for _ in range(H)]
visited = [[[-1 for _ in range(k+1) ]for _ in range(W)] for _ in range(H) ]
# y, x, res, k
Q = deque([[0, 0, 0]])
res = sys.maxsize
visited[0][0][0] = 0 # visited[H][W][K+1] : H : 세로, W : 가로, K : 말처럼 움직인 횟수
while Q:
    y, x, localK= Q.popleft() # 현재 좌표 (y,x), 말처럼 움직인 횟수 : localK
    # 말처럼 움직이는 경우
    if localK < k:
        for hy, hx in horse:
            X, Y= hx + x, hy + y
            # 범위 체크
            if 0 <= X < W and 0 <= Y < H:
                # 장애물 확인
                if zoo[Y][X] == 1: continue
                # 방문 확인
                if visited[Y][X][localK+1] != -1: continue
                # 능력 사용시
                Q.extend([[Y, X, localK+1]])
                visited[Y][X][localK+1] = visited[y][x][localK] + 1
	# 말처럼 움직이지 않은 경우
    for my, mx in monkey:
        X, Y = x + mx, y + my
        # 범위 체크
        if 0 <= X < W and 0 <= Y < H:
            # 장애물 확인
            if zoo[Y][X] == 1: continue
            # 방문 확인
            if visited[Y][X][localK] != -1: continue
            Q.extend([[Y, X, localK]])
            visited[Y][X][localK] = visited[y][x][localK] + 1
for i in range(k+1):
    if res > visited[H-1][W-1][i] > -1:
        res = visited[H-1][W-1][i]
if res == sys.maxsize:
    print(-1)
else:
    print(res)

---

참고 레퍼런스

1. https://regularmember.tistory.com/172

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