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

💡문제

백분 1600번 문제 링크

🍀풀이

원숭이의 이동방법은 인접한 칸과 말의 이동방법이 있다. 이때 원숭이는 k번 밖에 못간다.

코드

import sys
from collections import deque
input = sys.stdin.readline

k = int(input().rstrip())
w, h = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(h)]

# 원숭이 이동방법
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

# 말의 이동방법
hx = [-2, -1, 1, 2, 2, 1, -1, -2]
hy = [1, 2, 2, 1, -1, -2, -2, -1]

def bfs(n):
    queue = deque()
    queue.append((0, 0, n))
    
    # 말의 이동 방법 횟수 저장 3차원 방문 배열 선언
    visited = [[[0] * (n+1) for _ in range(w)] for _ in range(h)]
    
    while queue:
        x, y, n = queue.popleft()
        
        # 도착점에 오면
        if x == h-1 and y == w-1:
            return visited[x][y][n]
        
        # 횟수가 남아 있으면 말의 이동방법 진행
        if n > 0:
            for i in range(8):
                nx = x + hx[i]
                ny = y + hy[i]
                if 0 <= nx < h and 0 <= ny < w:
                    if graph[nx][ny] == 0 and visited[nx][ny][n-1] == 0:
                        queue.append((nx, ny, n-1))
                        visited[nx][ny][n-1] = visited[x][y][n] + 1
        
        # 끝나면 마저 실행
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if graph[nx][ny] == 0 and visited[nx][ny][n] == 0:
                    queue.append((nx, ny, n))
                    visited[nx][ny][n] = visited[x][y][n] + 1
    return -1
result = bfs(k)
print(result)

접근 방법과 풀이 거의 다 됐는데 자꾸 틀렸다고 나오길래 뭐지 했는데
visited[nx][ny][n-1] 이부분에서 n-1대신 n을 하고 있었네...헷갈린다 헷갈려,,, 그래도 슬슬 적응하고 있다!