[백준 - Python] 1600 - 말이 되고픈 원숭이

0. 문제 링크

 

 

 

www.acmicpc.net/problem/1600

1600번: 말이 되고픈 원숭이

---

1. 풀이 방법

 

 

단순 BFS를 하면 되는데, 추가로 내가 이미 방문한 곳보다 말을 적게 탔을 경우도 생각해봐야 한다.
또한 임계치보다 말을 적게 탔을 경우에는 말을 추가로 탈 수 있도록 처리함

아래에서 check 변수는 어느 지점까지 말을 탄 횟수이고, cur_k는 현재 내가 말을 탄 횟수

그 외엔 특별한 점 없음

---

2. 코드

 

 

import sys
from collections import deque


def sol():
    k = int(sys.stdin.readline())
    w, h = map(int, sys.stdin.readline().split())
    board = [[b for b in map(int, sys.stdin.readline().split())] for _ in range(h)]
    check = [[k + 1 for _ in range(w)] for _ in range(h)]

    dq = deque([[0, 0, 0]])
    dy, dx = [-1, 0, 0, 1], [0, 1, -1, 0]
    h_dy, h_dx = [-1, -2, -2, -1, 1, 2, 2, 1], [-2, -1, 1, 2, 2, 1, -1, -2]     # 말을 타는 경우
    cnt = 1

    while dq:
        for _ in range(len(dq)):
            y, x, cur_k = dq.popleft()
            if y == h - 1 and x == w - 1:
                print(cnt - 1)
                exit(0)
            if cur_k < k:       # 아직 임계치까지 말을 타지 않은 경우
                for i in range(8):
                    ny, nx = y + h_dy[i], x + h_dx[i]
                    if 0 <= ny < h and 0 <= nx < w and check[ny][nx] > cur_k + 1 and not board[ny][nx]:
                        # 기존에 방문한 곳보다 말을 적게 탔을 경우도 확인해야 함
                        dq.append([ny, nx, cur_k + 1])
                        check[ny][nx] = cur_k + 1
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                if 0 <= ny < h and 0 <= nx < w and check[ny][nx] > cur_k and not board[ny][nx]:
                    # 기존에 방문한 곳보다 말을 적게 탔을 경우도 확인해야 함
                    dq.append([ny, nx, cur_k])
                    check[ny][nx] = cur_k

        cnt += 1
    print(-1)


sol()

---

3. 마무리

 

 

확실히 조건을 찾는게 중요하다는 것을 깨달았다.