BOJ 14923 미로탈출

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

시간 1초, 메모리 512MB
input :

• N M(2 ≤ N ≤ 1000, 2 ≤ M ≤ 1000)
• Hx Hy(미로에 떨어진 위치. 1 ≤ Hx, Hy ≤ 1000)
• Ex Ey(미로의 탈출 위치. 1 ≤ Ex, Ey ≤ 1000)
• 1이 벽, 0이 빈 칸.(행렬 입력)

output :

• 최단경로 출력 , 불가능 하면 -1을 출력.

조건 :

---

Hx, Hy 와 Ex, Ey의 경우에 평소의 리스트 처럼 0, 0 시작이 아니기 때문에 그래프를 나타내는 리스트가 추가 공간이 필요함. 리스트의 바깥으로 나가는 경우에 대한 예외처리 다르게 필요.

2206 과 문제 구성이 거의 똑같다. 3차원 배열에 벽을 뚫을 수 있는 능력이 존재하는지에 따라 다르게 값을 저장해 나간다.

정답코드 :

import sys
from _collections import deque

N, M = map(int, sys.stdin.readline().split())
Hx, Hy = map(int, sys.stdin.readline().split())
Ex, Ey = map(int, sys.stdin.readline().split())
graph = [[-1] * (M + 1) for _ in range(N + 1)]
cache = [[[0] * 2 for _ in range(M + 1)] for _ in range(N + 1)]

for i in range(1, N + 1):
    data = list(map(int, sys.stdin.readline().split()))
    for j in range(len(data)):
        graph[i][j + 1] = data[j]

def BFS():
    q = deque([(Hx, Hy, 1)])
    cache[Hx][Hy][1] = 1

    while q:
        x, y, crash = q.popleft()
        if x == Ex and y == Ey:
            return cache[x][y][crash]
        dx = [1, -1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx > N or nx < 1 or ny > M or ny < 1:
                continue
            if graph[nx][ny] == 1:
                if crash and not cache[nx][ny][crash - 1]:
                    cache[nx][ny][crash - 1] = cache[x][y][crash] + 1
                    q.append((nx, ny, crash - 1))
                else:
                    continue
            elif graph[nx][ny] == 0:
                if not cache[nx][ny][crash]:
                    cache[nx][ny][crash] = cache[x][y][crash] + 1
                    q.append((nx, ny, crash))
ret = BFS()
if ret:
    print(ret - 1)
else:
    print(-1)