[백준] 1600번 말이 되고픈 원숭이 (python)

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

 

처음에 말처럼 이동하는 경우와 아닌 경우를 동시에 queue에 넣어서 돌렸고 문제 예제도 맞았다. 근데 제출하니까 틀려서 뭐가 문제지 하고 생각해 보니 말처럼 이동하면 안 되는 경우에 말처럼 이동한 후 visited를 True로 바꿔버려서 다른 경우를 고려하지 못하는 문제가 발생했다. 이 예외 상황을 처리하기 위해 2차원으로 관리하던 배열을 3차원으로 바꿨고, 그중 마지막 차원은 말처럼 이동한 횟수로 두었다.

 

문제가 조금 익숙하다고 느껴졌는데 2024 하반기 삼성 계열사 오후 2번 문제랑 결이 비슷하다.. 그 문제도 3차원으로 이동을 관리해야 해서 비슷하게 느껴졌다.

 

 

정답코드

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

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

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

mi = [-1, -2, -2, -1, 1, 2, 2, 1]
mj = [-2, -1, 1, 2, -2, -1, 1, 2]
visited = [[[False for _ in range(k+1)] for _ in range(w)] for _ in range(h)]


def bfs(si, sj):
    dq = deque([(si, sj, k, 0)]) # 앞의 0은 K 사용 횟수
    visited[si][sj][k] = True
    
    while dq:
        ci, cj, k_count, move = dq.popleft()
        
        if ci == h-1 and cj == w-1:
            return move
        
        if k_count: # 말처럼 이동하는 경우
            for m in range(8):
                nmi, nmj = mi[m] + ci, mj[m] + cj

                if 0 <= nmi < h and 0 <= nmj < w and not visited[nmi][nmj][k_count-1]:
                    if board[nmi][nmj] != 1:
                        visited[nmi][nmj][k_count-1] = True
                        dq.append((nmi, nmj, k_count-1, move+1))
        
        for d in range(4):
            ni, nj = di[d] + ci, dj[d] + cj
            
            if 0 <= ni < h and 0 <= nj < w and not visited[ni][nj][k_count]:
                if board[ni][nj] != 1:
                    visited[ni][nj][k_count] = True
                    dq.append((ni, nj, k_count, move+1))
        
    return -1

print(bfs(0, 0))