문제 링크
https://www.acmicpc.net/problem/1600
🕒 Python 풀이시간: 20분
import sys
from collections import deque
input=sys.stdin.readline
dx=[0,0,-1,1]
dy=[-1,1,0,0]
hdx=[-2,-1,1,2,2,1,-1,-2]
hdy=[1,2,2,1,-1,-2,-2,-1]
K=int(input())
W,H=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(H)]
visited=[[[-1]*W for _ in range(H)] for _ in range(K+1)]
q=deque()
q.append((0,0,K))
visited[K][0][0]=0
while q:
x,y,leftK=q.popleft()
if leftK>0:
for i in range(8):
nx=x+hdx[i]
ny=y+hdy[i]
if nx<0 or ny<0 or nx>=H or ny>=W:
continue
if visited[leftK-1][nx][ny]!=-1:
continue
if board[nx][ny]==1:
continue
visited[leftK-1][nx][ny]=visited[leftK][x][y]+1
q.append((nx,ny,leftK-1))
for i in range(4):
nx=x+dx[i]
ny=y+dy[i]
if nx<0 or ny<0 or nx>=H or ny>=W:
continue
if visited[leftK][nx][ny]!=-1:
continue
if board[nx][ny]==1:
continue
visited[leftK][nx][ny]=visited[leftK][x][y]+1
q.append((nx,ny,leftK))
answer=40001
for i in range(K+1):
if visited[i][H-1][W-1]!=-1:
answer=min(answer,visited[i][H-1][W-1])
if answer==40001:
print(-1)
else:
print(answer)말이 되고픈 원숭이: 최단 경로를 찾아라! 🐒🚀
말이 되고픈 원숭이가 K번 말처럼 즉, 나이트 처럼 이동할 수 있고 나머지는 사방으로 이동할 수 있는 문제이다. 이 때, 왼쪽 위에서 출발하여 오른쪽 아래까지 가는 최단 이동 수를 구하는 문제이다. 즉 최소 거리를 방법수로 탐색해 나가는 BFS 문제라는 점을 알 수 있다.
먼저 차원을 나누어야 한다. 왜냐하면 0~K번의 말의 이동을 사용한 상황에 따라 갱신되는 것이 장애물에 따라 달라지기 때문이다. 다행히 장애물이 막았을 때, 장애물도 뛰어넘을 수 있기 때문에 여기까지만 고려하면 된다. 차원을 나누어서 사용한 횟수에 따라 visited에 횟수를 BFS처럼 갱신해 나가면 된다. 여기서 단순히 leftK로 남은 횟수를 나타내서 visited를 생성하고 만약 leftK가 0보다 큰 경우, 즉 말의 이동을 사용한 경우에 한해서 8방향의 가짓수를 추가하였다. 이때, 8방향으로 나아갈 때는, leftK를 사용하기 때문에 leftK-1의 차원에 기록해 주어야 한다.
이렇게 전부 visited로 BFS로 마친 후, 각 차원에 따라 즉 사용한 횟수에 따라 최소 거리의 갱신값이 다르기 때문에 우리가 구하고자하는 도착지에 모든 visited값을 찾아서 answer로 최솟값을 갱신시켜준다. 만약 모든 차원의 visited가 갱신되지 않았다면 가지 못한 경우이기 때문에 -1을 출력해주고 그 이외에는 최솟값을 갱신해준다.
이렇게 Python으로 백준의 "말이 되고픈 원숭이" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊
