벽 부수고 이동하기

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

아이디어

맨 처음 생각했던 방법은 모든 벽 (1)을 길(0)으로 하나씩 바꿔보고 BFS를 하는 방식이었는데 벽의 최대 개수가 NM개이기 때문에 시간복잡도가 O(N^2M^2)가 되어 풀 수 없었다.

모든 벽을 부숴보면서 풀 수 없기 때문에 길을 가다 벽을 만났을 때 벽을 부순 적이 없다면 부수고 지나가고, 부순 적이 있다면 그 부분은 탐색을 하면 안 된다. 그런데 문제가 있다. 내가 벽을 부수고 온 건지 그냥 온 건지 알 수가 없다. 벽을 부쉈다는 상태를 기록해야 풀 수 있다.

어떻게 하면 벽을 부쉈다는 상태를 기록할 수 있을까? BFS를 할 때 큐에 다음 노드의 정보를 집어넣는 과정이 있다. 이 때 "벽을 부수고 왔으면 1, 벽을 부수지 않고 그냥 왔으면 0"이라는 상태를 함께 제공한다.

그리고, "벽을 부수고 온 경우에만 사용하는 그래프"를 따로 만들어서 사용한다. 원래 그래프에서 벽을 부수면, 원래 그래프의 벽은 그대로 두고 벽을 부수고 온 경우에만 사용하는 그래프의 같은 위치의 벽을 부수고 거기서부터 탐색한다.

그러면 벽을 부술 때마다 그래프를 하나씩 다시 만들어야하나? 생각할 수 있지만 하나만 더 만들어서 사용하면 된다.
현재 노드를 기준으로, 상하좌우 네 방향의 노드중 적절한 것을 골라 큐에 집어넣는데, 이 때 1이면 벽이니까 탐색하지 않고,(원본 그래프의 위치에 1이 있는지 본다. 누가 벽을 부숴놨을지도 모르기 때문) 1이 아닌 다른 숫자면 "현재 노드에 담긴 숫자"와 비교하여 차이가 1이 아니면 (방금 내가 지나온 길이면 차이가 1일 것이다. 숫자를 1씩 더해가며 몇 칸 이동했는지 기록하기 때문) 탐색한다. 즉, 재활용이 가능하다는 말이다.

말로 풀어 쓰니까 좀 어려운데 주석을 달아둔 코드를 보면 이해하기 쉬울지도?..

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
N, M = map(int, input().split())

graph = [[[] for _ in range(N)] for _ in range(2)]
for i in range(N):
    str = input()
    for c in str:
        for z in range(2):
            graph[z][i].append(int(c))

def bfs(graph):
    res = 987654321
    q = deque()
    q.append((0, 0, 0))
    graph[0][0][0] = 1
    while q:
        z, y, x = q.popleft()
        if y == N - 1 and x == M - 1:
            res = min(res, graph[z][y][x])
        # 벽을 부수고 온 경우
        if z == 1:
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                # 맵 밖으로 벗어났을 때
                if ny < 0 or nx < 0 or ny >= N or nx >= M:
                    continue
                # 벽 만났을 때 (원본 그래프로 체크)
                elif graph[0][ny][nx] == 1:
                    continue
                # 길 만났을 때
                elif graph[1][ny][nx] == 0:
                    graph[1][ny][nx] = graph[1][y][x] + 1
                    q.append((1, ny, nx))
                # 누가 지나온 길 만났을 때
                else:
                    # 내가 방금 밟은거 아니면
                    if graph[1][ny][nx] != graph[1][y][x] + 1:
                        graph[1][ny][nx] = graph[1][y][x] + 1


        else:
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                # 맵 밖으로 벗어났을 때
                if ny < 0 or nx < 0 or ny >= N or nx >= M:
                    continue
                # 벽 만났을 때 (원본 그래프로 체크)
                elif graph[0][ny][nx] == 1:
                    # 부순 적 없는 벽이면
                    if graph[1][ny][nx] == 1:
                        graph[1][ny][nx] = graph[0][y][x] + 1
                        q.append((1, ny, nx))
                # 길 만났을 때
                elif graph[0][ny][nx] == 0:
                    graph[0][ny][nx] = graph[0][y][x] + 1
                    q.append((0, ny, nx))
                # 지나온 길 만났을 때
                else:
                    continue
    return res


ans = bfs(graph)
if ans == 987654321:
    print(-1)
else:
    print(ans)

여담

3일 내내 나를 괴롭혔다.. 그래프 문제를 많이 풀어봐야겠다. 저렇게 기발한 생각은 어떻게 하는 걸까? ps 잘하는사람들 너무 부럽다.