BOJ 2206 벽 부수고 이동하기(Python 3)

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

단순 BFS문제이다.

배열을 3차원 배열 dist[n][m][2]로 만들어 주면 풀기 쉽다.

마지막 [2]는 벽을 부숴본 적이 없을 때/벽을 부숴본 적이 있을 때로 나눈 것이다.

코드 확인

from collections import deque
n,m=map(int,input().split())
S=[list(map(int,[*input()])) for k in range(n)]
D= [[[-1]*2 for j in range(m)] for i in range(n)]
D[0][0][0]=1
q=deque()
q.append((0,0,0))
dx,dy=[0,0,1,-1],[1,-1,0,0]
while q:
    x,y,z=q.popleft()
    for i in range(4):
        nx,ny=x+dx[i],y+dy[i]
        if 0<=nx<n and 0<=ny<m:
            if S[nx][ny]==0 and D[nx][ny][z]==-1:
                D[nx][ny][z]=D[x][y][z]+1
                q.append((nx,ny,z))
            if z==0 and S[nx][ny]==1 and D[nx][ny][z+1]==-1:
                D[nx][ny][z+1]=D[x][y][z]+1
                q.append((nx,ny,z+1))
if D[n-1][m-1][0]==-1:print(D[n-1][m-1][1])
elif D[n-1][m-1][1]==-1:print(D[n-1][m-1][0])
else:print(min(D[n-1][m-1]))