2206 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

from collections import deque
n,m = map(int,input().split())
graph = [ list(map(int,input())) for _ in range(n) ]
#print(graph)
#상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]
#벽을 부순것을 어떻게 표기 할 것인지가 핵심!!
#week5 PGS 경주로건설과 비슷한 발상
#조건을 체크하기 편하기 위해서 vsitied[x][y][z] 이렇게 방문여부 확인
visited = [[[0] * 2 for _ in range(m)] for _ in range(n)]
#print(visited)

def bfs(x,y,wall):
    q=deque()
    q.append((x,y,wall))
    #방문표시
    visited[0][0][0]=1
    #bfs루틴
    while q:
        x,y,z = q.popleft()
        #만약 n,m까지 갔다면 해당위치 거리까지 반환
        if x==n-1 and y ==m-1:
            return visited[x][y][z]
        
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            #범위안이야?
            if 0<=nx<n and 0<=ny<m:
                # 벽 없고, 방문한적 없어
                if graph[nx][ny] == 0 and visited[nx][ny][z] == 0:
                    #이동해야지 근데 ? visited에 숫자 추가해서 기록 아기상어2 참고
                    visited[nx][ny][z]= visited[x][y][z]+1
                    q.append((nx,ny,z))
                # 만약 벅있고, 벽을 부순적 없다면??
                elif graph[nx][ny]==1 and z==0:
                    #벽을 부수고 visited에 숫자 추가
                    #벽 부쉈으니깐 z = 1체크
                    visited[nx][ny][z+1] = visited[x][y][z]+1
                    q.append((nx,ny,z+1))
                    
    #끝까지 못간다면  -1 반환       
    return -1
#항상 시작은 000
print(bfs(0,0,0))