[Python] 백준 1600 (BFS)

문제 링크

Point (3차원 배열)

이 문제에서 그래프 탐색 시, 단순히 특정 좌표 칸에 방문했는지만 확인하는 것에 그치지 않음.
그 칸에 방문했을 때, 몇 번의 말 움직임을 이미 했는지 에 대한 정보도 고려함.

• 가령, graph[x][y]를 방문했을 때, 전에 1번 말 움직임 했는지와 2번 말 움직임 했는지가 다름.
  graph[x][y]를 2번 말 움직임으로 2번 이상 방문했을 때에는, 다시 고려할 필요 없어 탐색을 그만해도 되지만,
  말 움직임 횟수가 다른 상태에서 칸을 방문했을 때는 탐색을 이어나가야 함.

이런 방문을 체크하기 위해선 3차원 방문 처리 배열이 필요.
visited[x][y][k] = graph[x][y]를 k번의 말 움직임으로 방문한적이 있느냐를 뜻하는 3차원 배열을 사용.
나머진 그냥 bfs로 풀면 됨.

코드

import sys
from collections import deque

input = sys.stdin.readline


def bfs():
    horse_x = [-1, -2, -2, -1, 1, 2, 2, 1]
    horse_y = [-2, -1, 1, 2, 2, 1, -1, -2]
    dist_x = [-1, 1, 0, 0]
    dist_y = [0, 0, -1, 1]

    while q:
        x, y, k, cnt = q.popleft()
        if x == H - 1 and y == W - 1:
            print(cnt)
            exit(0)
        if k > 0:
            for dx, dy in zip(horse_x, horse_y):
                next_x, next_y = x + dx, y + dy
                if 0 <= next_x < H and 0 <= next_y < W:
                    if not graph[next_x][next_y]:
                        if not visited[next_x][next_y][k - 1]:
                            visited[next_x][next_y][k - 1] = True
                            q.append([next_x, next_y, k - 1, cnt + 1])
        for dx, dy in zip(dist_x, dist_y):
            next_x, next_y = x + dx, y + dy
            if 0 <= next_x < H and 0 <= next_y < W:
                if not graph[next_x][next_y]:
                    if not visited[next_x][next_y][k]:
                        visited[next_x][next_y][k] = True
                        q.append([next_x, next_y, k, cnt + 1])


if __name__ == '__main__':
    K = int(input())
    W, H = map(int, input().split())
    graph = []
    visited = [[[False for _ in range(K + 1)] for _ in range(W)] for _ in range(H)]  # 3차원 방문 처리 배열: visited[x][y][k] = graph[x][y]를 k번의 말 움직임으로 방문한적이 있느냐
    for _ in range(H):
        graph.append(list(map(int, input().split())))

    q = deque([[0, 0, K, 0]])  # x, y, 남은 말 움직임 횟수, 이동 횟수
    graph[0][0] = 1
    bfs()
    print(-1)