BOJ 14923 - 미로 탈출

문제

백준 온라인 저지 - 14923번

풀이 과정

시작 지점에서 목표 지점에 도달하는 최단 경로를 찾는 BFS 문제입니다.

단 벽이 존재할 경우 1회에 한해서 벽을 부수고 이동할 수 있기 때문에 상태 공간을 다음과 같이 정의합니다.

visit[x][y][magic] : (x, y) 지점에 남은 마법의 횟수 magic 을 이용하여 도달 한 경우가 있는지

이후 목표 지점에 도달하면 거리 바용을 반환하면 됩니다.

코드

import sys
from collections import deque

N, M = list(map(int, sys.stdin.readline().split()))
Hx, Hy = list(map(int, sys.stdin.readline().split()))
Ex, Ey = list(map(int, sys.stdin.readline().split()))
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():
    q = deque()
    visit = [[[0] * 2 for _ in range(M)] for _ in range(N)]

    q.append([Hx - 1, Hy - 1, 1, 0])
    visit[Hx - 1][Hy - 1][1] = 1

    while q:
        x, y, magic, cost = q.popleft()

        if [x, y] == [Ex - 1, Ey - 1]:
            return cost

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]

            if 0 <= nx < N and 0 <= ny < M:
                if visit[nx][ny][magic]:
                    continue

                if magic and board[nx][ny]:
                    visit[nx][ny][0] = 1
                    q.append([nx, ny, 0, cost + 1])
                elif not board[nx][ny]:
                    visit[nx][ny][magic] = 1
                    q.append([nx, ny, magic, cost + 1])

    return -1


def solution():
    answer = bfs()

    return answer


print(solution())