[Algorithm] 1600. 말이 되고픈 원숭이

1600: 말이 되고픈 원숭이(BFS)

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

• 문제 티어 : G3
• 풀이 여부 : Failed → Solved
• 소요 시간 : 38:25

정답 코드

from collections import deque

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

def bfs():
  visited = [[[False] * (K + 1) for _ in range(W)] for _ in range(H)] # x, y 위치, k번 말처럼 이동한 경우 방문 여부
  dq = deque([(0, 0, 0, K)]) # (x좌표, y좌표, 동작수, 남은 말 이동 횟수)

  dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
  kx, ky = [-2, -1, 1, 2, 2, 1, -1, -2], [1, 2, 2, 1, -1, -2, -2, -1]

  while dq:
    x, y, move, k_limit = dq.popleft()

    if x == H - 1 and y == W - 1:
      return move

    if k_limit > 0: # 말처럼 이동 처리
      for i in range(8):
        nx, ny = x + kx[i], y + ky[i]
        if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k_limit - 1] and arr[nx][ny] == 0:
          visited[nx][ny][k_limit - 1] = True
          dq.append((nx, ny, move + 1, k_limit - 1))

    for i in range(4): # 일반 이동 처리
      nx, ny = x + dx[i], y + dy[i]
      if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny][k_limit] and arr[nx][ny] == 0:
        visited[nx][ny][k_limit] = True
        dq.append((nx, ny, move + 1, k_limit))

  return -1

print(bfs())

접근 방식

말처럼 이동이 가능한 K번의 횟수를 초과할 경우, x, y 좌표의 값 업데이트를 kx, ky 에서 dx, dy로 바꿔주는 방식이다.

visited를 2차원 배열로 관리했었고, 말처럼 이동 가능한 횟수를 별도의 변수로 관리했었는데, 값 업데이트가 의도한대로 되지 않아서

visited 배열의 형태를 2차원 → 3차원 : x위치, y위치, k번 말처럼 이동한 경우 방문 여부 로 바꿔서 관리해줬다.

deque에 추가하는 자료 역시 (x좌표, y좌표, 동작수, 남은 말 이동 횟수) 로 바꿔줬더니 의도했던대로 동작한다!

배운점 또는 느낀점

W, H 범위 지정이 헷갈렸다. 그래서 index out of range가 여러번 떴었다 😅

범위 체크 잘 하기!