[알고리즘] BFS - 문제풀이 (백준 - 1261번)

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

1261번: 알고스팟

저번 BFS 문제에 이어서 대표적인 BFS 문제 풀이를 진행해보겠다. 

문제 

알고스팟 운영진이 모두 미로에 갇혔다. 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다. 

현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

---

풀이

최소 거리를 구하는 문제이기 때문에 BFS를 이용한다.

각 방을 노드로, 방과 방 사이를 이동하는데 부숴야하는 벽의 수를 노드 간 이동 비용이라고 했을 때,

벽이 없는 방(0)으로 이동하는데에는 비용이 0, 부숴야 하는 벽(1)으로 이동하는데에는 비용이 1 소모되는 0과 1의 비용을 가진 탐색이 된다.

(중요) 비용이 0과 1로 나뉘어져있을때에는 deque를 사용해서 매 노드를 탐색할 때마다 갈 수 있는 노드에 대한 비용이 0이면 앞에, 1이면 뒤에 추가해주며 탐색을 이어나가면 된다. 

 

즉, Queue를 활용하여 우선 탐색할 좌표를 앞으로 append, 나중에 탐색(비용이 필요한)할 좌표를 뒤로 append하여 최소 비용을 구한다. 

그렇게 하면 비용이 적은 경로부터 우선적으로 탐색하고, 가장 적은 비용에 대한 탐색이 끝나고 나서야 비로소 더 큰 비용의 경로를 탐색하기 시작하기 때문에 벽을 최소한으로 부수고 이동하는 경로를 찾을 수 있게 된다.

 

import sys
from collections import deque
 
n, m = map(int, sys.stdin.readline().split())
a = []
 
for i in range(m):
    a.append(sys.stdin.readline())

# 탐지하지 않은 영역을 -1로 표시하여 dist 리스트로 표현
dist = [[-1]*n for _ in range(m)]
dist[0][0] = 0

q = deque()

# 오른쪽, 왼쪽, 아래, 위
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q.append([0, 0])

while q:
    x, y = q.popleft()
    
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        
        if nx>=0 and nx<m and ny>=0 and ny<n:
            if dist[nx][ny] == -1:
                
                if a[nx][ny] == '0':
                    q.appendleft([nx, ny]) # 비용이 x(빈방인 경우) 우선탐색 할 수 있도록
                    dist[nx][ny] = dist[x][y] # 탐색한 자리에 비용 입력 

                elif a[nx][ny] == '1':  
                    q.append([nx, ny]) # 비용이 o(벽인 경우) 나중탐색 할 수 있도록
                    dist[nx][ny] = dist[x][y]+1 # 탐색한 자리에 비용(+1) 입력

print(dist[m-1][n-1])