(Python) 백준 1600 - 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

 

아이디어

 - 가중치가 없는 그래프에서 최단 경로를 구하는 문제이므로 BFS를 사용한다.

 - 각 칸의 방문 여부를 체크할 때, 말의 움직임 횟수에 따라 개별적으로 체크해줘야 한다.

 

코드

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

# 입력
k=int(input())
w,h=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]

# 방문여부를 말의 움직임 횟수에 따라 각각 체크
v=[[[0]*(k+1) for _ in range(w)] for _ in range(h)]

# 인덱스 4번 부터는 말의 움직임
dy,dx=[1,-1,0,0,2,2,1,1,-1,-1,-2,-2],[0,0,1,-1,-1,1,-2,2,-2,2,-1,1]

# (y좌표, x좌표, 사용한 말의 움직임 횟수) 의 형태로 큐에 삽입
q=deque([(0,0,0)])

# 시작지점 방문여부 체크
v[0][0][0]=1

# BFS
while q:
    y,x,c=q.popleft()
    if (y,x)==(h-1,w-1): break
    
    for i in range(12):
        ny,nx,nc=y+dy[i],x+dx[i],c+(i>3)
        
        # 사용한 말의 움직임 횟수가 제한횟수 미만일 때만 아래 코드 실행
        if i>3 and c>=k: break
        if 0<=ny<h and 0<=nx<w and not v[ny][nx][nc] and not a[ny][nx]:
            q.append((ny,nx,nc))
            v[ny][nx][nc]=v[y][x][c]+1
            
if v[h-1][w-1][c]: print(v[h-1][w-1][c]-1)
else: print(-1)

 

풀이는 떠올리기 쉬우나 실수할만한 포인트들이 다수 존재하는 문제인 것 같다.