백준 1600 | 말이 되고픈 원숭이 | python 풀이

 

문제

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

1600번: 말이 되고픈 원숭이

내 답안

# 1600 말이 되고픈 원숭이
from collections import deque

k = int(input().strip())
w, h = map(int, input().split())
horse_mv = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1), (1, 2),
            (2, 1)]  # 말이 움직이는 방식
monkey_mv = [(-1, 0), (1, 0), (0, 1), (0, -1)]  # 원숭이가 움직이는 방식

board = [list(map(int, input().split())) for _ in range(h)]
visited = [[[0] * w for _ in range(h)] for _ in range(k + 1)]  # 이동횟수 행, 열
d = deque([(0, 0, 0)])
flag = 0  # 도착여부
visited[0][0][0] = 1  # 시작 지점

while d:
  cnt, ch, cw = d.popleft()

  # 도착
  if (ch == h - 1 and cw == w - 1):
    print(visited[cnt][ch][cw] - 1)  # 시작지점 이동횟수 제외
    flag = 1
    break

  # 원숭이처럼 이동
  for i, j in monkey_mv:
    nh, nw = ch + i, cw + j
    if (0 <= nh < h and 0 <= nw < w and board[nh][nw] != 1
        and not visited[cnt][nh][nw]):
      visited[cnt][nh][nw] = visited[cnt][ch][cw] + 1
      d.append((cnt, nh, nw))

  # 말처럼 이동
  if cnt < k:
    for i, j in horse_mv:
      hh, hw = ch + i, cw + j
      if (0 <= hh < h and 0 <= hw < w and board[hh][hw] != 1):
        # 말처럼 움직인 횟수 증가 : 배열 차수 + 1
        if not visited[cnt + 1][hh][hw]:
          visited[cnt + 1][hh][hw] = visited[cnt][ch][cw] + 1
          d.append((cnt + 1, hh, hw))

if not flag:
  print(-1)

해설

다차원 배열을 이용한 bfs 문제다.

 

기본적인 풀이흐름은 일반적인 bfs와 동일하다.

목적지 도착 여부를 판단하는 flag 변수,

지점마다 방문 여부를 기록하는 visited 배열,

이동을 기록하는 deque를 활용해서 그래프 탐색을 시작한다. 

 

deque이 비워지기 전까지 목적지에 도착했는지 판단해서 알맞은 답을 출력해내면 된다. 

 

이때 일반적인 bfs와는 다르게 visited 배열에 추가적인 정보를 저장해야 한다. 말처럼 움직인 횟수에 제한이 있기 때문에 원숭이가 몇 번이나 말처럼 움직였는 지를 기록해야 한다. 

 

말처럼 움직일 수 있는 횟수를 k라고 했다.

따라서 주어진 w,h크기의 visited 배열을 (k+1)개 층층이 쌓아 올린다고 상상한다.

그렇다면 visited[1]은 말처럼 움직인 횟수가 1번일 때, visited[2]는 말처럼 움직인 횟수가 2번일 때의 bfs 방문 기록 배열이 된다. 

피드백

• 유사 문제를 푼 경험이 있어 다차원 배열로 방문 여부를 기록하는 아이디어는 쉽게 떠올랐다.
• bfs 탐색 시 원숭이처럼 이동하면서 동시에 말처럼 이동하는 것과 비교할 수 있는 방법이 떠오르지 않아서 네 방향으로 원숭이처럼 이동시킨 후에 조건이 되면 말처럼 이동시키는 방식으로 문제를 해결했다.