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

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

 

 

풀이

처음에 14502번 - 연구소 문제처럼 맵(그래프)을 하나하나 돌면서 벽이 있다면 그 벽을 부수고 bfs 돌려보고 최단거리가 아니면 다시 그 자리에 벽을 세우고 다른 벽을 부수어보는 방식으로 해결하려고 코드를 짰는데, 시간 초과 가 나왔고 두 번째 시도에는 틀렸습니다 가 나왔다. 그래서 다른 방법으로 시도해야겠다는 생각으로 다른 분들의 풀이 방법을 보았고 또, 2206번 문제 FAQ 글이 있길래 봤는데...

 

일단 이 해결 방식은 정답이 될 수 없다. 이유는 2가지가 있었는데, 첫 번째는 시간 복잡도가 너무 크게 나오는 것이다. 연구소 문제 같은 경우에는 N, M 범위가 작아서 하나하나 방문해도 시간 복잡도가 크지 않았지만 이 문제는 N, M의 범위가 1,000이라서 단순하게 생각해도 1000 * 1000 이라는 상당한 시간이 소요된다.
두 번째는 (N, M)으로 가는 길목이 벽으로 막혀있는 상황에서 그 벽까지 가는 최단 거리가 벽을 부순 경우와 부수지 않은 경우 둘 중 부순 경우가 최단 거리일 때, 이미 벽을 한 번 부쉈기 때문에 (N, M)으로 갈 수가 없어 -1을 출력하게 된다. 즉, 현재 가는 경로가 지금 당장 최단 거리는 아닐지라도 (N, M)으로 갈 수 있는 단 하나의 방법이라면 그 경로가 최단 거리가 되는 것이다. 이러한 이유로 처음 생각해낸 방법은 해결 방안이 될 수 없었다.

 

그럼, 이제 두 가지 문제점을 해결하면서 정답을 찾아보자. 먼저 첫 번째 문제점인 모든 요소의 벽을 허물어본다는 무작정 허물고 bfs를 돌려보는 것이 아닌 bfs를 먼저 돌려보고 그 과정에서 가는 경로에 벽이 있고, 이 경로는 벽을 허문 적이 없다면 허물어보자 로 해결할 수 있다. 즉, 맵(그래프) 각각의 요소에 경로에 따라 "벽을 허물었나?" 에 대한 정보를 주는 것이다. 하지만 이는 곧 두 번째 문제로 이어진다. 왜냐하면 (N, M) 지점이 벽으로 둘러져있을 때 (N, M) 지점 앞 벽까지 어떤 벽을 허물고 온 경로와 허물지 않고 온 경로 중 허문 경로가 더 최단 경로라면 이 경로의 각각의 길은 이미 방문한 것으로 기록되기 때문에 허물지 않은 경로가 재방문을 할 수 없게 된다. 즉, (N, M) 지점으로 갈 수 없게 된다. 그렇다면 방문 여부를 벽을 허문 경우와 허물지 않은 경우 둘로 나누어 주면 된다! 그러면 벽을 허문 경우에 먼저 방문하여 최단 거리를 만들었다해도 허물지 않은 경우가 뒤늦게 방문하여 (N, M) 지점으로 갈 수 있게 된다.

 

정리하자면, bfs 탐색을 돌리면서 각각의 경로에 벽을 허물고 가는 경로인지를 표시하고, 경로의 방문 여부를 허물고 가는 경우인지 허물지 않고 가는 경우인지 나누어 표시한다. 그리고 그 과정에서 (N, M) 지점으로 먼저 가는 경로가 최종적으로 최단 경로가 된다.

 

 

코드

import sys, copy
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
path = [list(map(int, input().rstrip())) for _ in range(N)]
visited =[[[0, 0] for i in range(M)] for _ in range(N)]
wasd = ((0, -1), (0, 1), (-1, 0), (1, 0))

def bfs(start_x, start_y):
    queue = deque()
    queue.append([start_x, start_y, 0])

    visited[start_y][start_x][0] = True
    dist = copy.deepcopy(path)
    dist[start_y][start_x] = 1

    while queue:
        x, y, wall_break = queue.popleft()
        
        if x == M-1 and y == N-1:
            return dist[y][x]

        for xx, yy in wasd:
            xx += x
            yy += y

            if (0 <= xx < M) and (0 <= yy < N):
                if path[yy][xx] == 0:
                    if not visited[yy][xx][wall_break]:
                        queue.append([xx, yy, wall_break])
                        visited[yy][xx][wall_break] = True
                        dist[yy][xx] = dist[y][x] + 1
                elif path[yy][xx] == 1 and wall_break == 0:
                    if not visited[yy][xx][0]:
                        queue.append([xx, yy, wall_break + 1])
                        visited[yy][xx][0] = True
                        dist[yy][xx] = dist[y][x] + 1
    
    return -1

print(bfs(0, 0))