백준 1600 말이 되고픈 원숭이

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1600

풀이

난이도 : Gold III

이 문제는 기본적인 bfs 문제를 조금 응용한 문제이다. 2차원 배열에서 한 칸씩 이동하는 것과 말이 이동하는 것을 동시에 생각하여야 한다. 또한 말이 이동하는 횟수가 정해져 있는 것을 생각해야 한다.

1) 기본적인 bfs를 구현한다.

2) visited를 3차원 배열로 변경하여 말이 이동할 수 있는 남은 횟수를 같이 기록할 수 있도록 한다.
-> 예) 남은 횟수 : 3, x 좌표 : 1, y 좌표 : 2 -> visited[3][1][2] = True

3) q를 한 번 돌 때마다 말이 이동할 수 있는 남은 횟수가 있다면 말이 이동하는 경우를 추가해 준다.

✔ 주의할 점

• result의 값을 처음에 0으로 초기화하고, bfs를 진행한 후 마지막에 result가 0 이면 -1을 출력하도록 하였을 때,
  2차원 배열이 하나만 주어졌을 경우(길이가 1, 1일 경우) -1을 출력하는 오류가 발생하니 주의하여야 한다.
  (해결 : result = -1로 초기화)

  
  

• python의 경우 bfs를 구현할 때, deque를 사용하면 된다.(일반 queue를 사용하면 오래걸림)

  
  

• 한 칸씩 이동할 때는 visited[s_count][nx][ny]를 참조하고, 말이 이동하는 경우에는 visited[s_count-1][nx][ny]를 참조해야 하는 것을 주의해야 한다. (말이 이동할 때는 횟수 차감이 이루어지기 때문)

코드

from collections import deque
import sys

input = sys.stdin.readline
k = int(input())
w, h = map(int, input().split())
array = []

for _ in  range(h):
    array.append(list(map(int, input().split())))

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
steps = [[-2, -1], [-2, 1], [-1, -2], [-1, 2], [1, -2], [1, 2], [2, -1], [2, 1]]

q = deque()
q.append((0, 0, 0, k))
visited = [[[False] * w for _ in range(h)] for _ in range(k+1)]
visited[k-1][0][0] = True
result = -1

while q:
    x, y, count, s_count = q.popleft()

    if x == h-1 and y == w-1:
        result = count
        break

    if s_count > 0:
        for step in steps:
            nx = x + step[0]
            ny = y + step[1]

            if nx < 0 or ny < 0 or nx >= h or ny >= w:
                continue
            if visited[s_count-1][nx][ny] or array[nx][ny] == 1:
                continue
            visited[s_count-1][nx][ny] = True
            q.append((nx, ny, count+1, s_count-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[s_count][nx][ny] or array[nx][ny] == 1:
            continue
        visited[s_count][nx][ny] = True
        q.append((nx, ny, count+1, s_count))

print(result if result != -1 else -1)