[BOJ / Python] 2206번: 벽 부수고 이동하기

문제: BOJ 2206번

풀이

14940번 과 비슷하지만 단 한가지 차이로 난이도가 엄청 차이나는 문제이다.
벽을 하나를 부숴버릴 수 있다니..
결국 벽을 부수기 전과 후로 나뉘니 방문처리 배열을 삼중으로 만들어버리면 처리할 수 있지 않을까?

최종코드

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

n,m=map(int,input().split())
ar=[]
visited=[[[0]*2 for i in range(m)]for i in range(n)]
visited[0][0][0]=1		#방문처리 겸 경로 길이 저장용 배열.
for i in range(n):
    ar.append(list(map(int,input().rstrip())))
d=[[0,1],[1,0],[0,-1],[-1,0]]		#탐색을 위한 상수
brk=0								#부쉈는지 확인하기 위한 변수
def bfs():
    q=deque()
    q.append((0,0,0))
    while q:
        dx,dy,brk = q.popleft()		#큐에서 꺼냄
        if dx==n-1 and dy==m-1:		#꺼낸 값이 목적지일때 최단경로 반환 
            return visited[dx][dy][brk]
        for xx,yy in d:
            nx=dx+xx
            ny=dy+yy
            if nx<0 or ny<0 or nx>=n or ny>=m:
                continue			#범위 벗어나면 제외
            
            if ar[nx][ny]==1 and brk==0:
                visited[nx][ny][1]=1+visited[dx][dy][brk]	
                q.append((nx,ny,1))
               # 벽을 만났는데 벽을 아직 부수지 않았다면..?
               # 벽을 부순 세계로 넘어간다. 더이상 벽을 부수지 못하게 brk값을 넘겨준다.
               
            if ar[nx][ny]==0 and visited[nx][ny][brk]==0:
                visited[nx][ny][brk] = 1+visited[dx][dy][brk]
                q.append((nx,ny,brk))
                # 벽이 아니고 방문하지도 않았다면 전위치 최단경로에 +1한 값 저장.
                
    return -1	#목적지에 도달하지 못하고 탐색이 끝났다면 -1 반환!
print(bfs())
    

벽 부순다는게 아직도 어렵다. 벽 하나 부수는거로 머리아픈데 나중엔 더 부수던데...