백준 2206번 : 벽 부수고 이동하기 in Python

2206번: 벽 부수고 이동하기

 

www.acmicpc.net

이 문제는 이전에 다루었던 2178번 문제인 미로 탐색 문제와 유사하나 벽을 한 번 부수고 이동할 수 있을 경우 최단 거리를 구하는 문제이다.

이전 미로 탐색 문제와 유사하게 N*M 행렬을 만들되 벽을 한 번 부수는 경우를 추가로 고려하기 위해 N*M 행렬을 두 개를 준비해 visit이라는 N*M*2 행렬을 만든다. 즉, 하나는 벽을 부수지 않는 경우, 하나는 벽을 한 번 부순 경우에 해당한다.

그 다음에는 미로 탐색과 동일하게 BFS 코드를 작성하나 추가로 만약 원소 주변에 벽이 있을 경우 벽을 부수지 않은 경우에 한해서 벽을 부수고 그 벽의 entry도 BFS 과정에 추가한다. 즉, queue에 벽의 index와 벽을 부쉈다는 의미의 index를 넣고 visit 행렬에도 벽을 부순 경우의 N*M 행렬에서 그 벽의 entry에 값을 추가한다. 

그리고 이제는 N*M 행렬이 두 개가 되어 BFS가 끝나면 (N-1, M-1)에 값이 두 개가 생긴다. 만약 여기의 값이 0인 경우는 (0, 0)에서 출발한 결과 (N-1, M-1)에 도달하지 못한 경우인데, 두 개의 값이 각각 0인 경우과 그렇지 않은 경우로 나눠 각 경우에 대해 최단 거리를 구하면 된다. 그러나 이렇게 하기 보다는 BFS의 while loop에서 (N-1, M-1) entry를 처음으로 발견할 경우 그 entry를 출력하고, 발견하지 못할 경우 -1을 출력하도록 하는 것이 코드 복잡도 면에서 더 간단하다.

이를 코드로 구현하면 다음과 같다.

import sys
from collections import deque
N, M = map(int, input().split())
maze = []
for _ in range(N):
    s = input()
    arr = []
    for c in s:
        arr.append(int(c))
    maze.append(arr)
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
queue = deque()
# N*M 행렬을 두 개 가진 visit 행렬을 만들어 
# 하나는 벽을 부수지 않은 경우, 하나는 벽을 부순 경우로 나눈다.
visit = [[[0]*2 for _ in range(M)] for _ in range(N)]
def BFS():
    global N
    global M
    queue = deque()
    queue.append([0, 0, 1])
    visit[0][0][1] = 1
    while len(queue) > 0:
        [x, y, z] = queue.popleft()
        # 도착점을 최초로 발견할 경우 바로 반환한다.
        if x == N-1 and y == M-1:
            return visit[x][y][z]
        for k in range(4):
            next_x = x + dx[k]
            next_y = y + dy[k]
            if 0<=next_x<N and 0<=next_y<M:
                # 벽을 부수지 않은 상태에서 벽을 발견한 경우 벽을 부수고 나아간다.
                if maze[next_x][next_y] == 1 and z == 1:
                    queue.append([next_x, next_y, z-1])
                    visit[next_x][next_y][z-1] = visit[x][y][z] + 1
                # 일반적인 경우
                elif maze[next_x][next_y] == 0 and visit[next_x][next_y][z] == 0:
                    queue.append([next_x, next_y, z])
                    visit[next_x][next_y][z] = visit[x][y][z] + 1
    # 도착점에 도달하지 못한 경우 -1을 반환한다.
    return -1            
print(BFS())