[백준] 1600번 : 말이 되고픈 원숭이

1600번: 말이 되고픈 원숭이

1600번: 말이 되고픈 원숭이

🤔 문제분석

너비우선탐색과 방문배열을 K차원으로 두어 문제를 해결하였습니다. 너비우선탐색을 하게되면 x,y좌표에서 i번 움직였을때가 가장 최소거리임으로 3차원 배열을 만듭니다.

시작점으로부터 원숭이가 이동하는 방법과 말과 이동하는 방법 모두 탐색합니다.

💻 코드

import sys
from collections import deque

input = sys.stdin.readline

K = int(input())
W, H = map(int, input().split())
horse_moves = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1), (1, 2), (2, 1)]
moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
table = []

for _ in range(H):
    table.append(list(map(int, input().split())))
    
queue = deque([(0, 0, 0, K)])
visited = [[[False] * W for _ in range(H)] for _ in range(K+1)]

def is_range(y, x):
    return H > y >=0 and W > x >=0

is_founed = False
while queue:
    y, x, cost, cnt = queue.popleft()
    
    if y == H-1 and x == W-1:
        is_founed = True
        print(cost)
        break
    
    # 말로 움직인다.
    if cnt > 0:
        for dy, dx in horse_moves:
            ny, nx = y + dy, x + dx
            new_cost = cost + 1
            if is_range(ny, nx) and not visited[cnt-1][ny][nx] and table[ny][nx] == 0:
                visited[cnt-1][ny][nx] = True
                queue.append((ny, nx, new_cost, cnt-1))
                
    # 기본으로 움직인다.
    for dy, dx in moves:
        ny, nx = y + dy, x + dx
        new_cost = cost + 1
        if is_range(ny, nx) and not visited[cnt][ny][nx] and table[ny][nx] == 0:
            visited[cnt][ny][nx] = True
            queue.append((ny, nx, new_cost, cnt))
    
if not is_founed:
    print(-1)

🎯 피드백 및 개선사항

방문하는 방식을 3차원으로 두어 문제를 해결하는게 이문제의 핵심 포인트입니다.