[python] 백준 14923 미로 탈출

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

14923번: 미로 탈출

문제 해결

• 전형적인 BFS문제
• 그러나 편하게 BFS를 돌리면 시간초과가 난다.(벽을 한 번만 깰 수 있다는 것을 활용해야함)
• 그래서 array를 3차원으로 해서 n*m*2차원을 만든다. (board[i][j][k]: (i,j)에 있고 k개의 magic 사용 가능)
• 도착점 왔으면 최소이동횟수이므로 cnt출력하면 끝

 

CODE

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

def bfs(y,x):
    que = deque()
    que.append((y,x,0,1))
    visited = [[[False for _ in range(2)] for _ in range(m)] for _ in range(n)]
    visited[y][x][1] = True
    while que:
        y, x, cnt, magic = que.popleft()
        if (y, x) == (ey, ex):
            return cnt
        for i in range(4):
            ny, nx = y+dy[i], x + dx[i]
            if 0<=ny<n and 0<=nx<m:
                if visited[ny][nx][magic]:continue
                if board[ny][nx] == 1 and magic==1:
                    visited[ny][nx][0] = True
                    que.append((ny,nx,cnt+1,magic-1))
                elif board[ny][nx] ==0:
                    visited[ny][nx][magic] = True
                    que.append((ny,nx,cnt+1,magic))
    return -1
if __name__=='__main__':
    n, m = map(int, input().split())
    hy, hx = map(int, input().split())
    ey, ex = map(int, input().split())
    hy, hx, ey, ex = hy-1, hx-1, ey-1, ex-1
    board = [list(map(int, input().split())) for _ in range(n)]
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    print(bfs(hy,hx))