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

• Problem Link : https://www.acmicpc.net/problem/2206

문제

흔히 알려진 미로찾기 문제의 일종으로 길이 '0', 벽을 '1'로 나타낸다. 이 때 벽을 한 개까지 부수고 이동할 수 있을때 최단 경로를 구하여라.

입력

• 첫째 줄, N, M이 주어진다.
• 둘째 줄, N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

• 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

풀이

최단 경로라는 단어가 보이자마자 BFS 기법을 고려해야한다. 단순한 미로찾기와 이 문제의 차이는 벽을 한 칸 부수고 이동할 수 있다는 뜻이다. 당연하게도 입력의 모든 벽들을 하나씩 0으로 바꾸면서 BFS를 돌리면서 최단 경로를 찾으면 시간 초과가 발생하므로 BFS를 진행하면서 동시에 벽을 부숴야한다.

벽을 부수는 방법을 처음에는 굉장히 간단하게 생각했다. 기존에 미로찾기 문제에서의 BFS의 방식은 아래와 같다.

def bfs(graph):
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]

    queue = deque()
    queue.append([0, 0, 0])
    graph[0][0] = "0"

    while queue:
        i, j, dist = queue.popleft()

        if i == n - 1 and j == m - 1:
            print(dist[i][j])
            exit()

        for d in range(4):
            ni = i + di[d]
            nj = j + dj[d]

            if ni < 0 or n <= ni or nj < 0 or m <= nj:
                continue

            if graph[ni][nj] == "0":
                queue.append([ni, nj, dist + 1])
                graph[ni][nj] = "-"
    return

큐에서 현재 위치를 뽑아온 후 di, dj를 이용해 사방을 확인한다. 확인 중에 갈 수 있는 아직 방문하지 않은 좌표가 있다면 해당 길의 좌표를 큐에 추가해놓는다. 이 때 추가한 좌표는 방문한 것이라고 취급해 그래프의 값을 구별할 수 있도록 바꿔준다. 이후 다시 돌아가 큐에서 현재 위치의 좌표를 꺼내는 과정을 반복한다.

visited 변수를 구현해도 되지만 dfs와 달리 길을 찾는 bfs는 다시 돌아가지 않는다. 한 스텝이 진행할 때마다 가능한 모든 경로로 진행되기 때문이다.

위와 같은 기존의 미로찾기에서 벽을 하나만 부술 수 있기 때문에 벽을 부쉈는지 안부쉈는지를 변수 하나를 추가로 만들어 확인하면서 벽을 부순적이 없으면 next 좌표가 벽, "1"이어도 진행할 수 있도록 코딩했다. 하지만 반례가 존재했고 그 원인은 다음과 같았다.

기존의 미로찾기는 내가 방문한 좌표들을 "-"로 바꾸면서 방문했다는 것을 표시하면서 가서 다시 방문하지 않는다. 하지만 이 문제에서는 벽을 부수고 진행한 경우와 벽을 부수지 않고 진행한 경우가 같은 좌표에서 만날 수 있다.

예를 들어 다음과 같은 입력이 온다고 가정해보자.

이 때 BFS 방식을 진행하면 아래와 같이 벽을 부수지 않은 케이스와 벽을 부순 케이스가 부딪히게 된다.

위 예는 단순히 시작하자마자 오른쪽 벽을 한칸 부수고 나간 경로와 0을 따라간 경로의 충돌만 나타낸 모습이다. 실제로는 거의 모든 벽들이 0의 진행과 만나면 다음 스텝에서 한칸씩 다 부서지기 때문에 4열까지의 벽은 거의 다 "-"로 변한 상태이다.

즉, 위와 같은 문제가 발생한 원인은 벽을 부수고 진행한 경로가 기존의 "0"을 타고 가는 경로조차 모두 방문했다고 표시해서 그렇다 실제로 위 경우에서 도착 지점에 가기 위에서는 먼저 벽을 부수고 진행하면 안되고 마지막에 도착지점에서 벽을 부숴야한다.

1) 벽을 부수고 진행하는 경우와 2) 0을 따라가는 경로를 구분할 필요가 있다. 따라서 기존 미로 찾기 코드와 동일하게 0을 따라가다가 벽을 부술 수 있는 상황에서 벽을 만나면 그 이후의 경로는 다른 배열에서 진행하도록 진행했다. 이렇게 하면 0을 계속해서 따라가면서 벽을 부수는 경우는 다른 배열에서 진행되므로 결국 모든 0을 방문하면서 경로를 탐색할 수 있게 된다.

"벽을 부수는 수 많은 경우가 있는데 그러면 그 경로들끼리 또 충돌이 발생하지 않나요?" 라는 질문을 할 수 있으나, 이는 문제에서 벽을 하나만 부술 수 있다는 조건 때문에 상관이 없다. 이미 벽을 부수고 진행한 경로는 또 다른 벽을 부수고 해당 경로로 진행할 필요가 없기 때문에 (최단 경로를 구하는 문제이기 때문에) 하나의 배열에서 벽을 부순 모든 경로를 확인해도 문제가 없다.

아래 코드와 같이 벽을 부순 경로들은 graph[1]에서 벽을 부수지 않고 0만 따라가는 경로들을 graph[0]에서 진행하도록 하였다. 결국 이 문제는 2개의 2차원, 즉 3차원 BFS 문제임을 알 수 있다.

코드

import sys
from collections import deque
import copy

input = sys.stdin.readline

def bfs() :
    
    q = deque()
    q.append([0, 0, 0, 0])
    
    di = [1,0,-1,0]
    dj = [0,1,0,-1]
    
    graph[0][0][0],graph[1][0][0] = "-","-"
        
    while q :
        i, j, wall, dist = q.popleft()
        
        if i == n-1 and j == m-1 :
            print(dist+1)
            exit()
            
        for d in range(4) :
            ni = i + di[d]
            nj = j + dj[d]
            
            if ni < 0 or n<= ni or nj < 0 or m <= nj :
                continue
            
            if graph[wall][ni][nj] == '0' :
                graph[wall][ni][nj] = "-"
                q.append([ni, nj, wall, dist+1])
                
            if graph[wall][ni][nj] == "1" and wall == 0 :
                graph[0][ni][nj] = "-"
                graph[1][ni][nj] = "-"
                
                q.append([ni, nj, 1, dist+1])
        
    print(-1)

n,m = map(int,input().split())
temp = []
for _ in range(n) :
    temp.append(list(input().strip()))


graph = [temp, copy.deepcopy(temp)]

bfs()