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

백준 1600. 말이 되고픈 원숭이

어려운 문제였는데 백준 문제 중에 비슷한 문제를 풀어본 적이 있어서 꽤 수월하게 풀었다. 벽 부수기 문제와 굉장히 비슷해서 풀이방식을 참고해서 풀었다.

💡 문제

원숭이가 가장 위 왼쪽에서 가장 아래 오른쪽으로 이동하려고 한다.
기본적으로 상하좌우로 움직일 수 있고, 체스의 나이트 움직임으로 k번 움직일 수 있다.
이러한 조건에서 원숭이가 목표 지점에 도달하기까지의 최소 이동 수를 구해야 한다.

💡 아이디어

위에서 말했듯이, 백준 문제 중 벽 부수기 문제의 풀이를 참고했다.

특정한 이동 방식에 횟수가 정해져있을 때, 3차원 배열을 활용한다. 즉, 방문 처리 배열을 3차원으로 나타내는데, visited[열][행][이동수]로 이해하면 된다.

예를 들어, 원숭이가 말의 움직임으로 이동해서 격자판[2][4]에 도달했고, 이제까지 말의 움직임으로 1번 움직였다고 가정하자. 그럼 visited[2][4][1] = visited[x][y][z]+1 처리로 해주면 된다. (x, y, z는 queue.popleft()의 결과이다. 즉 이동 전의 자리)

당연히 deque()를 사용했고, popleft()하여 원숭이의 위치가 가장 아래 오른쪽이면 visited[x][y][z]-1을 출력한다. (이동 불가능한 경우는 -1 출력)

💡 코드

from collections import deque

# 입력값
k = int(input())
m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우, 체스 나이트 이동
dist = [[1,0],[0,1],[-1,0],[0,-1]]
horse = [[-2,-1], [-2,1],[-1,-2],[-1,2],[2,-1],[2,1],[1,-2],[1,2]]

def bfs():
  visited = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]
  queue = deque()
  queue.append([0,0,0])
  visited[0][0][0] = 1

  while queue:
    x, y, z = queue.popleft()

    # 목표 지점에 도달하면 return
    if x==n-1 and y==m-1:
      return visited[x][y][z]-1

    # 상하좌우로 이동
    for (i,j) in dist:
      dx, dy = x+i, y+j
      if 0<=dx<n and 0<=dy<m and not visited[dx][dy][z] and not graph[dx][dy]:
        visited[dx][dy][z] = visited[x][y][z]+1
        queue.append([dx,dy,z])

    # 말 이동 수보다 작을 경우에만 이동
    if z<k:
      for (hi, hj) in horse:
        hx, hy = x+hi, y+hj
        if 0<=hx<n and 0<=hy<m:
          if not graph[hx][hy]:
            # z+1번째 말처럼 이동하는 중
            if not visited[hx][hy][z+1]:
              visited[hx][hy][z+1] = visited[x][y][z]+1
              queue.append([hx,hy,z+1])

  return -1

# 정답 출력
print(bfs())