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

문제

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

입력

• 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

출력

• 첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

입력 예제

1
4 4
0 0 0 0
1 0 0 0
0 0 1 0
0 1 0 0

2
5 2
0 0 1 1 0
0 0 1 1 0

출력 예제

4

-1

 

문제 풀이

• 말의 움직임은 k번까지만 가능하므로 말과 원숭이의 움직임을 따로 체크
• 3차원 배열을 사용하여 말의 움직임으로 이동했다면 visited[y][x][k + 1]의 형식으로 체크할 수 있음
  • 말의 움직임으로 이동했을 때 cnt 증가
• 모든 움직임을 마친 후 목적지에 도달했다면 이동 횟수 리턴
• 목적지에 도달하지 못했다면 -1리턴

코드

from collections import deque
# 말의 움직임
horse = [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,-2],[2,-1],[2,1],[1,2]]

# 상하좌우
dy = [-1,1,0,0]
dx = [0,0,-1,1]

k = int(input())
w, h = map(int,input().split())
graph = []
visited = [[[0] * (k + 1) for _ in range(w)] for _ in range(h)]
for _ in range(h):
    graph.append(list(map(int,input().split())))

def bfs(y,x, cnt):
    queue = deque()
    queue.append((y,x,cnt))
    visited[y][x][cnt] = 1
    while queue:
        y, x, cnt = queue.popleft()
        # 종료조건
        if y == h - 1 and x == w - 1:
            return visited[y][x][cnt] - 1
        # 원숭이 이동
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if graph[ny][nx] == 0 and not visited[ny][nx][cnt]:
                    visited[ny][nx][cnt] = visited[y][x][cnt] + 1
                    queue.append((ny, nx, cnt))

        # 말 이동
        if cnt < k:
            for (hy, hx) in horse:
                ny = y + hy
                nx = x + hx
                if 0 <= ny < h and 0 <= nx < w:
                    if graph[ny][nx] == 0 and not visited[ny][nx][cnt + 1]:
                        visited[ny][nx][cnt + 1] = visited[y][x][cnt] + 1
                        queue.append((ny, nx, cnt + 1))

    return -1

print(bfs(0,0,0))

---

전형적인 BFS 문제

벽 부수기 문제와 유사하다

유사 문제

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

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