[Python] 백준 2206 벽 부수고 이동하기

문제 보러 가기

N×M의 행렬로 표현되는 맵에서 0은 이동할 수 있는칸, 1은 벽(이동할 수 없는 칸)을 나타낸다.
단, 벽을 부수고 이동할 수 있는 기회가 1번 주어지므로 부셨을 때 이동경로가 짧아진다면 부셔도 된다.
(1, 1)에서 시작하여 (N,M)까지 가는데 최단거리를 출력하면 된다.

풀이 과정

이 문제는 칸이 1인 벽을 딱 한번 부술수 있다. 그래서 한번 부수는 걸 어떻게 표현할 까 고민하다가 첨에는 n*m 행렬에서 값이 1인 칸을 하나씩 찾아서(따로 전용 메서드를 만들어서) queue에 넣어서 구현할라 했지만 시간 초과가 나왔다.

그래서 벽을 부쉈는지의 여부를 3차원 행렬로써 나타내게 되었다.
벽 부수기 없이 나타낸다면 visit[x][y] 라고 표현할 수 있지만 z를 추가함으로써 0은 안부숨, 1은 부숨을 표현할 수 있다.

즉, visited[x][y][0]은 안부순 경로, visited[x][y][1]은 부순 경로.
중간에 벽을 부순 경로는 그 이후의 경로부터는 벽을 지나갈 수 없으므로 벽이 아닌곳들만 탐색하면 되고, 중간에 벽을 부수지 않은 경로는 그 이후의 경로에서 벽을 부술 수 있는 선택권이 주어진다.

정답 코드

import sys
input=sys.stdin.readline
from collections import deque
def BFS(x,y,z):
    dq=deque()
    dq.append((x,y,z))
    while dq:
        x,y,c=dq.popleft()
        if x == n-1 and y == m-1:
            return visit[x][y][c]
        for i in range(4):
            xx=x+dx[i]
            yy=y+dy[i]
            if xx<0 or xx>=n or yy < 0 or yy>=m:
                continue
            if a[xx][yy] == 1 and c == 0:
                visit[xx][yy][1] = visit[x][y][0]+1
                dq.append((xx,yy,1))
            elif a[xx][yy]==0 and visit[xx][yy][c]==0:
                visit[xx][yy][c]= visit[x][y][c]+1
                dq.append((xx,yy,c))
    return -1
                            
n,m=map(int, input().split())
a=[list(map(int, input().rstrip())) for _ in range(n)]

visit=[[[0]*2 for _ in range(m)] for _ in range(n)]
visit[0][0][0]=1




dx=[-1,0,1,0]
dy=[0,1,0,-1]

print(BFS(0,0,0))