[알고리즘] 백준 1600 말이 되고픈 원숭이 / 파이썬

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

 

2206번 문제와 아주 유사하다 응용해서 풀어주면 된다

방문을 체크하는 ck배열을 삼중배열로 만들어서 말처럼 이동한 경우/ 원숭이로 이동한 경우를 구별한다

x, y좌표로 말처럼 k번 이동했으면 ck[x][y][k]에 이동거리가 저장된다

x, y좌표로 원숭이로 이동했으면 k는 변하지 않는다

그리고 (H, W)까지 갔다면 저장했던 거리를 리턴, 아니라면 -1을 리턴해 출력해준다

 

from collections import deque

hx, hy = [-2, -2, -1, 1, 2, 2, -1, 1], [-1, 1, -2, -2, -1, 1, 2, 2]
dx, dy = [-1, 0, 1, 0], [0, -1, 0, 1]
def sol():
    ck = [[[0]*(K+1) for _ in range(W)] for _ in range(H)]
    while q:
        x, y, k = q.popleft()
        if x == (H-1) and y == (W-1): return ck[x][y][k]
        for i in range(4):
            xx, yy = x + dx[i], y + dy[i]
            if xx < 0 or xx >= H or yy < 0 or yy >= W: continue
            if ck[xx][yy][k] or Map[xx][yy]: continue
            ck[xx][yy][k] = ck[x][y][k] + 1
            q.append([xx, yy, k])
        if k == K: continue
        for i in range(8):
            xx, yy = x + hx[i], y + hy[i]
            if xx < 0 or xx >= H or yy < 0 or yy >= W: continue
            if ck[xx][yy][k+1] or Map[xx][yy]: continue
            ck[xx][yy][k+1] = ck[x][y][k] + 1
            q.append([xx, yy, k+1])
    return -1

K = int(input())
W, H = map(int, input().split())
Map = [list(map(int, input().split())) for _ in range(H)]
q = deque()
q.append([0, 0, 0])
print(sol())