[Python/파이썬] 백준 14923번 미로 탈출

14923번: 미로 탈출

 

코드

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

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

n, m = map(int, input().split())
hx, hy = map(int, input().split())
ex, ey = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]

dp = [[[int(1e9)]*2 for _ in range(m+1)] for _ in range(n+1)]
dp[hx][hy] = [0, 0]
q = deque([(hx, hy, False)])
while q:
    x, y, broke = q.popleft()
    if x == ex and y == ey:
        break
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 < nx <= n and 0 < ny <= m:
            if not broke:   # 벽 아직 안 뚫음
                if maze[nx-1][ny-1] == 0 and dp[nx][ny][0] > dp[x][y][0]+1:   # 이번에도 안 뚫음
                    dp[nx][ny][0] = dp[x][y][0]+1
                    q.append((nx, ny, broke))
                if maze[nx-1][ny-1] == 1 and dp[nx][ny][1] > dp[x][y][0]+1:  # 이번에 뚫음
                    dp[nx][ny][1] = dp[x][y][0]+1
                    q.append((nx, ny, True))
            elif broke and maze[nx-1][ny-1] == 0 and dp[nx][ny][1] > dp[x][y][1]+1:   # 이미 뚫은 적 있음
                dp[nx][ny][1] = dp[x][y][1]+1
                q.append((nx, ny, broke))

print(min(dp[ex][ey][0], dp[ex][ey][1]) if dp[ex][ey][0] != int(
    1e9) or dp[ex][ey][1] != int(1e9) else -1)

 

dp 배열

dp 배열은 (hx, hy)에서 출발하여 각 칸까지 가는 가장 빠른 경로의 길이를 저장할 것인데, 단 한 번 벽을 깰 수 있는 기회가 있으므로 아직 벽을 깬 적 없는 경우의 거리와 깬 적 있는 경우의 거리로 나누어 저장한다.

예를 들어, dp[x][y][0]은 (x, y)까지 오면서 벽을 깨지 않고 온 최단 거리, dp[x][y][1]은 (x, y)까지 오면서 벽을 깬 적 있는 최단 거리이다.

 

BFS

BFS를 이용하여 (hx, hy)에서 (ex, ey)까지의 최단 거리를 구한다. q에는 (x좌표, y좌표, 벽을 뚫은 적 있는지 여부)를 넣는다. 다음 칸으로 이동할 때는 3가지 경우로 나누어서 이동 가능 여부를 확인해야 한다.

 

① 이전에도 벽을 뚫은 적이 없고 이번에도 안 뚫는 경우

② 이전에 뚫은 적이 없지만 이번에 뚫는 경우

③ 이전에 뚫은 적이 있는 경우

 

이 3가지 경우로 나누어서 가능한 경우에만 q에 (nx, ny)를 넣고, dp[nx][ny][0] 또는 dp[nx][ny][1] 값을 다시 넣어준다.