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

1일 1PS 40일차!

📚 문제

---

골드 3

• BFS 문제

💡 풀이 과정

---

1. 원숭이와 말의 움직임을 설정한다.
2. k 가 남아있다면 말의 움직임을 추가해 bfs 를 진행한다.
3. 같은 곳을 방문했다면 k 가 많이 남아있는 것을 사용한다.

📌포인트

---

• dx, dy
  • dx = […], dy = […]
  • move = [[…], […]]
  • dx, dy 세트가 두 개 이상인 경우에는 아래의 경우가 더 편한다.
• visited
  • visited 를 bool 로 초기화했다가 같은 곳을 방문하더라도 k 가 많이 남은 움직임이 우선되어야하기에 남은 k 를 사용한다.
  • 이때 0 으로 초기화 시 k = 0 인 경우와 구분되지 않기에 음수로 초기화해야한다.
• min_move
  • W, H 가 200 이하이기에 min_move 를 단순하게 400 으로 설정했다가 3%에서 계속 오답 발생
  • 999로 설정하니 34% 에서 오답이 발생하고 999999로 하니 정답처리 되었다.
  • 리을자로 계속 움직인다고 했을 때 최대 move 는 400을 당연히 넘어가기 때문에 오답이 맞다.
  • 최대, 최소는 sys.maxsize 를 사용하는 것이 옳다.

💻 코드

---

import sys
from collections import deque

monkey_move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
horse_move = [[1, 2], [1, -2], [2, 1], [2, -1], [-1, 2], [-1, -2], [-2, 1], [-2, -1]]

K = int(input())
W, H = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(H)]
visited = [[-1 for _ in range(W)] for _ in range(H)]

queue = deque()
queue.append([0, 0, 0, K])
min_move = sys.maxsize

while queue:
    x, y, cnt, k = queue.popleft()

    if x == H -1 and y == W - 1 and cnt < min_move:
        min_move = cnt

    if cnt < min_move:
        if k > 0:
            for move in horse_move:
                nx = x + move[0]
                ny = y + move[1]
                if 0 <= nx <= H - 1 and 0 <= ny <= W - 1 and visited[nx][ny] < k - 1 and board[nx][ny] == 0:
                    visited[nx][ny] = k - 1
                    queue.append([nx, ny, cnt + 1, k - 1])

        for move in monkey_move:
            nx = x + move[0]
            ny = y + move[1]
            if 0 <= nx <= H - 1 and 0 <= ny <= W - 1 and visited[nx][ny] < k and board[nx][ny] == 0:
                visited[nx][ny] = k
                queue.append([nx, ny, cnt + 1, k])


if min_move == sys.maxsize:
    min_move = -1

print(min_move)