[백준][1261] 알고스팟

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

문제

미로에 갇혀있을때 벽을 부수면서 진행할 수 있다. 이 때 도착지점까지 최소 몇 개의 벽을 부수어야하는지 구하여라. 시작점과 도착 지점은 항상 뚫려있다.

입력

• 첫째 줄, 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N이 주어진다.
• 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다.

출력

• 첫째 줄, 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.

풀이

BFS 문제이지만 이 문제의 경우 최소한의 벽을 부수어야한다는 조건이 있으므로 벽을 적게 부순 경로를 우선해서 진행시켜야한다. 이렇게 우선순위, 가중치가 있는 BFS는 0-1 BFS 방식으로 해결할 수 있다.

0-1 BFS

0-1 BFS란?

• 0-1 BFS는 다익스트라에 BFS를 결합한 방법으로 임의의 가중치에 따라 원소를 덱의 맨 앞이나 뒤에 넣는 것이다. 0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 풀 수 있게 된다.

• 보편적으로 사용하는 다익스트라 알고리즘의 시간 복잡도가 $O(ElogE)$ 혹은 $O(ElogV)$인데 0-1 BFS를 사용하면 단지 $O(V+E)$의 선형 시간 복잡도로 문제를 해결할 수 있기 때문이다.

0-1 BFS의 동작

1. 덱의 front에서 현재 노드를 꺼낸다.
2. 연결된 인접 노드를 살펴본다.
3. "현재 노드까지 소비된 비용 + 그 노드를 향하는 가중치 < 해당 노드까지 가는데 소비된 비용"을 만족하면 소비된 비용을 갱신해준다.
4. 노드가 갱신된 상태에서 만약 그 노드를 향하는 가중치가 0이면 덱의 front, 1이면 덱의 back에 삽입하도록 한다.
5. 덱에서 더 이상 꺼낼 노드가 없을 때까지 위 과정을 반복한다.

$O(V+E)$의 증명

0-1 BFS를 수행하면 가중치가 1인 간선을 0번 거쳐간 노드 - 가중치가 1인 간선을 1번 거쳐간 노드 - ··· - 가중치가 1인 간선을 E번 거쳐간 노드

이런 식으로 비용이 적은 경로부터 탐색을 하게 되기 때문에 특정 간선을 2번 이상 지나가는 경우가 없다. = $O(E)$

똑같이 모든 정점도 2번 이상 경유하는 경우가 없으므로 덱 크기는 최대 |$V$|이다. = $O(V)$

따라서 0-1 BFS는 $O(V)+O(E) = O(V+E)$의 시간 복잡도를 가지게 된다.

따라서 이 문제의 경우 벽이 있는 경우 가중치가 1, 벽이 없는 경우 0의 가중치를 갖는 그래프라고 생각할 수 있다. 쉽게 말하면 벽을 적게 부순 원소를 앞에, 벽을 추가적으로 부순 원소를 뒤에 넣으면서 큐를 진행한다. (그렇게 되면 벽을 덜 부순 경로가 먼저 진행된다.)

또한 경로가 진행되면서 방문 표시를 해놓으면서 벽을 덜 부순 경로가 이미 지나고 난 경로는 이후에 벽을 부순 경로가 왔을 시 이미 벽을 덜 부순 경로가 지나간 길이므로 더 이상 확인할 필요가 없다.

위에서 $O(V+E)$의 증명에서 언급했듯이 특정 간선을 2번 이상 지나가는 경우가 없다.

따라서 이렇게 가중치가 필요한 BFS의 문제의 경우는 가중치에 따라 덱의 앞과 뒤에 삽입하는 0-1 BFS 알고리즘을 사용하면 쉽게 해결할 수 있다.

코드

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

# input
m, n = map(int,input().rstrip().split())
graph = [list(input().rstrip()) for _ in range(n)]
visited = [[False] * m for _ in range(n)]

# bfs
def bfs() :
    di = [1, 0, -1, 0]
    dj = [0, 1, 0, -1]
    
    q = deque()
    q.append([0, 0, 0])
    while q :
        i, j, wall = q.popleft()

        if i == n-1 and j == m-1 :
            return wall
        
        for d in range(4) :
            ni = i + di[d]
            nj = j + dj[d]
            
            if 0 <= ni < n and 0 <= nj < m and not visited[ni][nj] :
                visited[ni][nj] = True
                if graph[ni][nj] == '0' :
                    q.appendleft([ni,nj,wall])
                if graph[ni][nj] == '1' :
                    q.append([ni,nj,wall+1])
                    
print(bfs())