BOJ 백준 파이썬 2206 벽 부수고 이동하기

아주 쉬운 문제다.

전형적인 3차원 배열을 이용하는 문제

z=0(벽을 부순 횟수) 으로 시작해서 삼차원 배열의 disit 배열을 채워주면 된다.

*dist[z][x][y]= 벽을 z번 부셨을 때 (0,0)에서 (x,y)까지 가는 최단 거리

 

import sys
from collections import deque
from itertools import combinations
from typing import List, Literal
 
 
 
if __name__=='__main__':
    sys.stdin=open("input2.txt", "rt")
    
    n,m=map(int,input().split()) ##n=행,m=열
 
    board=[list(map(int,input())) for _ in range(n)]
 
    q=deque()
 
    dx=[0,0,-1,1]
    dy=[-1,1,0,0]
 
    dist=[[[-1]*m for _ in range(n)] for _ in range(2)]
    q.append((0,0,0)) ##(z,x,y)
    dist[0][0][0]=1
    while q:
        z,x,y=q.popleft()
 
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
 
            if 0<=nx<n and 0<=ny<m:
                if z ==0: ##벽을 뚫을 수 있음
                    if board[nx][ny]==1: ##벽일 경우
                        if dist[z+1][nx][ny]==-1:
                            dist[z+1][nx][ny]=dist[z][x][y]+1
                            q.append((z+1,nx,ny))
                    else: ##빈 칸일 경우
                        if dist[z][nx][ny]==-1:
                            dist[z][nx][ny]=dist[z][x][y]+1
                            q.append((z,nx,ny))
 
                else: ##벽을 뚫지 못함
                    if board[nx][ny]==0:
                        if dist[z][nx][ny]==-1:
                            dist[z][nx][ny]=dist[z][x][y]+1
                            q.append((z,nx,ny))
 
    res=float('inf')
    for z in range(0,2):
        if dist[z][n-1][m-1]!=-1:
            res= min(res,dist[z][n-1][m-1])
 
    if res==float('inf'):
        print(-1)
    else:
        print(res)