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

# # 1600 말이 되고픈 원숭이
from collections import deque
K = int(input())
W,H = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(H)]

stack = deque()
stack.append((0,0,0,K))

visited = [[[0 for z in range(K+1)] for y in range(W)] for _ in range(H)]
visited[0][0][0] = 1
horse_move = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
move = [(-1,0),(1,0),(0,-1),(0,1)]
result = -1
while stack:
    x,y,cnt,horse_cnt = stack.popleft()
    if x+1 == H and y+1 == W:
        result = cnt
        break
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if 0<=nx<H and 0<=ny<W:
            if not arr[nx][ny]:
                if not visited[nx][ny][horse_cnt]:
                    stack.append((nx,ny,cnt+1,horse_cnt))
                    visited[nx][ny][horse_cnt] = 1
    if horse_cnt:
        for dx,dy in horse_move:
            nx = x + dx
            ny = y + dy
            if 0<=nx<H and 0<=ny<W:
                if not arr[nx][ny]:
                    if not visited[nx][ny][horse_cnt-1]:
                        stack.append((nx,ny,cnt+1,horse_cnt-1))
                        visited[nx][ny][horse_cnt-1] = 1



print(result)

이 문제는 두가지의 이동방식이 있고, 그것을 구분해서 BFS를 해주면 된다. 하지만 여기서 주의할 점은 다음과 같다.

 

방문 표시를 체크를 하는데 주의를 해야한다.

 

 

1

4 4

0 0 0 0

0 0 0 0

0 0 1 1

0 0 1 0

 

위와 같이 되어 있다고 했을시, 방문표시를 따로 구분하지 않고 한가지로 했을시에는, 말로 왔는지, 원숭이로 왔는지 정확히 모르기 때문에 원하는 답이 안나올 수 있다.

 

그래서 visitied를 기존의 x,y 좌표 뿐만아니라 말의 이동회수를 기준까지 포함해서, 방문표시를 해주었다. 이부분만 조심해주면, 문제를 풀 수 있다.