[백준 2206번] 벽 부수고 이동하기 (python, bfs)

www.acmicpc.net/problem/2206

 

2206번: 벽 부수고 이동하기

 

vis 배열을 3차원으로 만들고 세 번째 인자 c가 1이면 뚫은 벽, 아니면 뚫지 않은 벽이다. 

 

벽을 뚫을 필요가 없을 때는 일반적인 bfs를 해주고 이미 한번 뚫은 뒤에는 (c가 1인채로 온 경우에는 현재 위치가 0인 경우에만 지나갈 수 있다)

 

벽을 뚫을 경우에는 현재 위치가 1(벽)이고 c가 0인 경우이다. 

 

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

dx,dy=[0,0,-1,1],[1,-1,0,0]
n,m=map(int,input().split())
a=list(list(map(int,input().strip())) for _ in range(n))
# 3차원 배열 만들기
vis=[[[0]*2 for _ in range(m)] for _ in range(n)]

def bfs():
    dq=deque()
    dq.append((0,0,0)) # y,x,0(벽 뚫기)
    vis[0][0][0]=1
    while dq:
        y,x,c=dq.popleft();
        if y==n-1 and x==m-1:
           return vis[y][x][c]

        for i in range(4):
            yy=y+dy[i]
            xx=x+dx[i]
            if yy<0 or yy>=n or xx<0 or xx>=m: continue
            if vis[yy][xx][c]: continue
            if a[yy][xx]==0:
                vis[yy][xx][c]=vis[y][x][c]+1
                dq.append((yy,xx,c))
            elif c==0:
                vis[yy][xx][1]=vis[y][x][c]+1
                dq.append((yy,xx,1))

result=bfs()
print(result) if result else print(-1)