[acmicpc] 2206. 벽 부수고 이동하기(python)

최단 경로 -  bfs 이용

3차원 배열을 사용하여 풀었다.

• visit[row][col][0] : 방문한 길 중에 벽을 부순 적이 있는 경우
• visit[row][col][1] : 방문한 길 중에 벽을 부순 적이 없는 경우

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

N,M=map(int,input().split())
arr=[list(input().strip()) for _ in range(N)]
visit=[[[0]*2 for _ in range(M)] for _ in range(N)]
dirs=[(1,0),(0,1),(-1,0),(0,-1)]
q=deque()
visit[0][0][1]=1
q.append((0,0,1))

def bfs():
    while q:
        r,c,z=q.popleft()
        if r==N-1 and c==M-1:
            return visit[r][c][z]
        for i in range(4):
            nr,nc=r+dirs[i][0],c+dirs[i][1]
            if 0>nr or nr>=N or nc<0 or nc>=M: continue
            if arr[nr][nc]=='0' and visit[nr][nc][z]==0:
                visit[nr][nc][z]=visit[r][c][z]+1
                q.append((nr,nc,z))
            if z>=1 and arr[nr][nc]=='1' and visit[nr][nc][z-1]==0:
                visit[nr][nc][z-1] = visit[r][c][z] + 1
                q.append((nr, nc, z-1))
    return -1
print(bfs())

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

2206번: 벽 부수고 이동하기