[문제 바로가기] https://www.acmicpc.net/problem/1261
📌문제 설명
알고스팟 운영진이 모두 미로에 갇혔다. 미로는 NxM 크기이며, 총 1x1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.
알고스팟 운영진은 여러명이지만, 항상 모두 같은 방에 있어야 한다. 즉, 여러 명이 다른 방에 있을 수는 없다. 어떤 방에서 이동할 수 있는 방은 상하좌우로 인접한 빈 방이다. 즉, 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.
벽은 평소에는 이동할 수 없지만, 알고스팟의 무기 AOJ를 이용해 벽을 부수어 버릴 수 있다. 벽을 부수면, 빈 방과 동일한 방으로 변한다.
만약 이 문제가 알고스팟에 있다면, 운영진들은 궁극의 무기 sudo를 이용해 벽을 한 번에 다 없애버릴 수 있지만, 안타깝게도 이 문제는 Baekjoon Online Judge에 수록되어 있기 때문에, sudo를 사용할 수 없다.
현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다.(1, 1)과 (N, M)은 항상 뚫려있다.
출력
첫째 줄에 알고스팟 운영진이 (N, M)으로 이동하기 위해 벽을 최소 몇 개 부수어야 하는지 출력한다.
💡 문제 풀이
최소의 벽을 부수어 (1, 1)에서 (N, M)으로 이동해야 한다.
따라서, 무조건 벽을 부수는 것이 좋은 방법은 아니다!
벽을 부수고 최단거리로 이동하는 방법보다는 이동거리가 길어도 벽을 부수지 않는 방법이 더 우선순위가 높다.
가능한 경로를 탐색하기 위해서 BFS 알고리즘을 사용하였다.
이 때, 벽을 부수지 않은 이동에 우선순위를 두기 위해서 heapq를 사용하였다.
기존의 BFS에서는 큐(queue) 자료구조에 (행, 열)을 담아서 탐색하였다면, 이번 문제에서는 힙(heapq)에 (벽을 부순 횟수, 행, 열)을 담아 '벽을 부순 횟수'를 기준으로 최소힙을 만들었다.
따라서, 벽을 부분 횟수가 가장 적은 자료부터 나와(heappop) 탐색을 진행하고 최종 목적지인 (N, M)에 도착했을 때 벽을 부순 횟수 값을 출력하면 된다.
코드는 다음과 같다.
import sys, heapq
M, N = map(int, input().split())
d = [(-1, 0), (1, 0), (0, 1), (0, -1)]
maps = [list(map(int, ' '.join(sys.stdin.readline().split()))) for _ in range(N)]
heap = []
heapq.heappush(heap, (0, 0, 0))
visited = [[0] * M for _ in range(N)] # 방문 여부 표시(NxM 배열)
visited[0][0] = 1 # 출발지점 방문 표시
while heap:
w, r, c = heapq.heappop(heap)
if r == N-1 and c == M-1: # 목표지점(N, M)에 도착하면 w 출력
print(w)
break
for idx in range(4): # 4방향 탐색
nr = r + d[idx][0]
nc = c + d[idx][1]
if 0 <= nr < N and 0 <= nc < M: # NxM 범위 확인
if maps[nr][nc] and not visited[nr][nc]: # 벽 & 방문 X
heapq.heappush(heap, (w+1, nr, nc)) # 벽을 부순 횟수 + 1
visited[nr][nc] = 1
elif not maps[nr][nc] and not visited[nr][nc]: # 빈 방 & 방문 X
heapq.heappush(heap, (w, nr, nc))
visited[nr][nc] = 1
