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

📖 문제

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

💻 내 코드

import sys
from collections import deque

k = int(sys.stdin.readline())

w, h = map(int, sys.stdin.readline().split())
mlist = [list(map(int, sys.stdin.readline().split())) for _ in range(h)]

dist = [[1e9] * w for _ in range(h)]

# 사방 탐색
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 말처럼 움직일 때
dxh = [1, 2, 2, 1, -1, -2, -2, -1]
dyh = [2, 1, -1, -2, -2, -1, 1, 2]

# 거리를 3차원 배열에 저장해줄 것임
visited = [[[0] * (k + 1) for _ in range(w)] for _ in range(h)]


def monkey():
    queue = deque([])
    queue.append((0, 0, k)) # 현재 위치와 horse 남은 횟수 append

    while queue:
        x, y, horse = queue.popleft()
        if x == h - 1 and y == w - 1: # 도착하면
            print(visited[x][y][horse]) 
            return
        if horse > 0: # 말처럼 움직일 수 있는 횟수가 남았다면
            for i in range(8):
                nx = x + dxh[i]
                ny = y + dyh[i]
                if 0 <= nx < h and 0 <= ny < w and mlist[nx][ny] == 0:
                # 인덱스 범위 내에 있고 평지일 때
                    if visited[nx][ny][horse - 1] == 0:
                        # 현재 위치를 더 적은 수의 말의 움직임으로 아직 방문하지 않았다면
                        visited[nx][ny][horse - 1] = visited[x][y][horse] + 1
                        # 1 더해줌
                        queue.append((nx, ny, horse - 1))
                    else: continue
                else: continue

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and mlist[nx][ny] == 0:
                if visited[nx][ny][horse]==0:
                    visited[nx][ny][horse] = visited[x][y][horse] + 1
                    queue.append((nx, ny, horse))

                else: continue
            else: continue

    print(-1) # 도착할 수 없는 경우


monkey()

💡 풀이

• 2차원 배열로 해결해보려고 하다가 모르겠어서 다른 사람들 코드 참고
• 다들 3차원 배열 사용해서 3차원 배열로 해결
• horse는 bfs를 돌면서 하나씩 줄여줌
• 만약 더 작은 횟수로 그 위치를 방문할 수 있다면 3차원 배열의 horse-1(현재 남은 횟수)에 해당 하는 곳에서 갱신