벽 부수고 이동하기 - 2206

1. 개요

문제 링크: https://www.acmicpc.net/problem/2206

2. 코드

from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input())) for _ in range(n)]
queue = deque([[0, 0, 0]])

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

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

while len(queue) != 0:
    y, x, breaked = queue.popleft()
    if x == m-1 and y == n-1:
        min_val = count_graph[breaked][y][x]
        break
    for i in range(4):
        nX = x + dx[i]
        nY = y + dy[i]
        if 0 <= nX < m and 0 <= nY < n:
            if graph[nY][nX] == 0 and count_graph[breaked][nY][nX] == 0:
                queue.append([nY, nX, breaked])
                count_graph[breaked][nY][nX] = count_graph[breaked][y][x] + 1
            if graph[nY][nX] == 1 and count_graph[breaked][nY][nX] == 0 and breaked == 0:
                queue.append([nY, nX, 1])
                count_graph[1][nY][nX] = count_graph[breaked][y][x] + 1


if n == m == 1:
    print(1)
elif min_val == 10000 or min_val == 0:
    print(-1)
else:
    print(min_val)

3. 풀이 메모

첫 번째 시도는 매 분기마다(= 벽을 부술 때마다) 새로운 count_graph를 복사해 별도로 관리하는 것이었다. 하지만 최악의 경우 약 10^12개의 int형 변수를 저장해야 하므로 당연히 메모리 초과가 발생했다.

풀이를 찾아본 결과, 매번 새로운 count_graph를 생성해줄 필요 없이 그냥 '벽을 뚫은 경우' 에 대해서만 별도의 count_graph를 만들면 해결됐다. 어차피 벽을 뚫은 경우 이후에는 무조건 길을 따라 가야 하므로, 이에 대한 로직도 '0' 을 따라가는 경우로 포함시키면 해결된다.

여러 개의 '벽을 뚫은 분기' 가 하나의 count_graph를 사용하는 것이 괜찮은가? 에 대해서도 걱정이 있을 수도 있지만, 우리는 BFS를 사용하고 있다. 즉, 여러 분기가 동시에 작동을 하더라도 방문한 적이 있으면 고려를 하지 않기 때문에 중복 카운팅의 문제도 없으며, Breadth-first의 방향성이 어느쪽이건 상관이 없다. 미로 문제에서 사용된 BFS는 이러한 원리로 거리의 최소값을 계산하므로 크게 걱정할 필요는 없다.

4. 코멘트

벽을 두번 뚫는 경우도 벽을 두번 뚫은 경우에 대해서 새로운 count_graph를 정의해주면 되지 않을까? 하는 막연한 생각도 든다. BFS를 응용할 줄 알아야 풀 수 있는 문제 같다.