🥚문제

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

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline
from collections import deque

def bfs():
    # visited[r][c][k] = (r, c)에 능력을 k번 사용해서 왔을 때, 말의 움직임 횟수
    visited = [[[-1]*(K+1) for _ in range(W)] for _ in range(H)]
    q = deque([(0, 0, 0, 0)]) # (r, c, 움직임횟수, 능력사용횟수)
    visited[0][0][0] = 0

    # 상하좌우
    dr = [0, 0, -1, 1]
    dc = [-1, 1, 0, 0]
    # 말의 움직임
    kr = [-2, -2, -1, -1, 1, 1, 2, 2]
    kc = [1, -1, 2, -2, 2, -2, -1, 1]

    while q:
        r, c, move, count = q.popleft()
        # 상, 하, 좌, 우
        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]
            if 0 <= nr < H and 0 <= nc < W:
                if board[nr][nc] == 0 and visited[nr][nc][count] == -1:
                    visited[nr][nc][count] = move + 1
                    q.append((nr, nc, move + 1, count))

       
        if count < K:
            # 말의 움직임
            for i in range(8):
                nr, nc = r + kr[i], c + kc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if board[nr][nc] == 0 and visited[nr][nc][count+1] == -1:
                        visited[nr][nc][count+1] = move + 1
                        q.append((nr, nc, move + 1, count + 1))

    # visited[H-1][W-1]에서 값이 -1이 아닌 것 중 최소값을 구한다
    candidates = []
    for x in visited[H-1][W-1]:
        if x > -1:
            candidates.append(x)
    if candidates:
        return min(candidates)
    return -1



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

print(bfs())

---

🧂아이디어

BFS

참고: https://yabmoons.tistory.com/48

• 일반적인 BFS처럼 이미 방문한 위치를 스킵하고 탐색한다면 오답이 출력된다!

• 어떤 위치까지 도달했을 때, 능력을 몇 번 써서 도착했는지에 따라 구분해서 동작 횟수를 구해줘야 한다.

• 따라서, visited를 3차원으로 구성한다.
  visited[r][c][count] = 능력을 쓴 횟수가 count일 때 (r, c)위치까지 가는 총 동작의 횟수

🔽 visited를 3차원으로 구성해서 풀었던 또다른 탐색 문제

[백준 2206] 벽 부수고 이동하기 ❗❗