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

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

2206번: 벽 부수고 이동하기

bfs를 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약해보면, N*M의 0과 1로 표현된 array가 주어집니다. 이때 1은 벽을 의미하는데 (1,1)에서 (N,M)으로 이동할 때, 벽을 최대 1개까지 부수고 이동이 가능합니다. 이 때, 최단거리를 출력하는 문제입니다. 만약 최단거리가 없다면 -1을 출력해야합니다.

 

<Solution>

이 문제는 기존 bfs에서 주로 두는 visited array를 한 차원 확장시켜야 하는 문제입니다. 

 

왜 확장을 시켜야 하는지 생각해봅시다. 같은 칸이라도 한칸을 부수고 와서 도착하는 경우와, 한칸을 부수지 않고 도착하는 경우가 다르기 때문입니다. 

조금더 부연설명을 붙이면, 

두가지 path 모두 저 형광색으로 색칠된 칸을 지나고나서 이후로 더 이동해야 합니다. 이때, 이후의 경로에서 벽을 부수어야 훨씬 빠르게 가는 길이 등장한다고 생각해봅시다. 그렇다면 이미 일찍 벽을 부수어버린 빨간색 path는 그때 엄청난 손해를 보게 되고 결과론적으로 주황색 길이 더 빨라질 수도 있기 때문입니다.

 

따라서 기존 bfs에서 visited array를 3차원으로 확장시켜서 구현을 하면 됩니다.

 

실제 구현은 아래와 같습니다.

import sys
from collections import deque
N, M = list(map(int,sys.stdin.readline().rstrip().split()))

# build array
array = []
for _ in range(N):
    array.append(list(map(int,list(sys.stdin.readline().rstrip()))))

# right down up left
d_row = [0, 1, 0, -1]
d_column = [1, 0, -1, 0]

def outofblock(row_size,column_size, row_index, column_index): # num row, num column index index
    return row_index<0 or row_index>row_size-1 or column_index<0 or column_index>column_size-1

# bfs
# build visited array
visited = [[[False] * M for _ in range(N)] for _ in range(2)]
# range(2) is used for break wall = 0 or 1 at that moment

q = deque([[0, 0, 0, 0]]) # row, column, breakwall_cnt, move_cnt

while(q):
    # print(q)
    r, c, bw, mc = q.popleft()
    if r == N-1 and c == M-1:
        print(mc+1)
        exit()

    if not visited[bw][r][c]:
        visited[bw][r][c] = True
    else:
        continue
    
    for i in range(4):
        new_r = r+d_row[i]
        new_c = c+d_column[i]

        # can move?
        if not outofblock(N,M,new_r,new_c):
            # 0 case
            if not visited[bw][new_r][new_c] and array[new_r][new_c] == 0:
                q.append([new_r, new_c, bw, mc+1])
            # 1 case
            elif bw == 0 and not visited[bw][new_r][new_c] and array[new_r][new_c] == 1:
                q.append([new_r, new_c, bw+1, mc+1])

print(-1)