알고스팟

왼쪽 상단의 점 부터 오른쪽 하단의 점 까지 이동하는데 부숴야 하는 벽의 최소 개수를 구하는 문제이다.

• 기존에 BFS에서 선입선출의 deque를 사용했던것과 달리 이 문제에서는 heapq를 사용해서 구현한다. 벽을 최소로 부수면서 이동해야 하기 때문에, 해당 점 까지 이동하는데 부숴야하는 벽의 수가 최소인 점부터 탐색해 나가는 것이다.

• 이 문제에서는 최소로 부순 벽의 개수만 구하면 되기에 어떤 점을 먼저 탐색하는지는 그리 중요하지 않다. 그래서 heapq를 사용할 수 있는 것이다.

• 또한, 기존에 BFS를 할 때는 벽이 나타나면 해당점을 아얘 탐색하지 않았지만, 이 문제에서는 벽이 있는 칸도 탐색해나간다. 대신, 벽이 나타나면 부수는 벽의 개수에 1을 추가해서 heapq에 넘긴다. 벽을 부수지 않은 점부터 모두 탐색하고 후순위로 탐색되는 것이다.

아래의 그림을 살펴보자.

• 첫 번째 지도에서는 벽을 부수지 않고 목적지까지 도착할 수 있다. 파란색 1로 표시된 칸들은 heapq에 추가되어 자신의 차례를 기다리지만, 0들에 의해 계속 순서가 밀려 결국 목적지에 도착하기전에 pop되지 못한다.

• 오른쪽 상단 지도에서는 벽을 부수지 않고 목적지까지 갈 방법이 없다. 따라서, 출발지와 벽들 사이에 있는 ‘0’인 칸들이 모두 pop된 후, ‘1’인 칸들의 순서가 되어 BFS가 진행되게 된다.

• 왼쪽 하단 지도에서는 벽을 한번 부수고, 목적지까지 도착할 수 있다. ‘2’로 표시된 파란점의 차례가 오기 전에 목적지에 먼저 도착한다.

• 오른쪽 하단 지도에서는 벽을 한번 부숴서는 목적지까지 도착할 방법이 없다. 벽을 한 번 부수고 갈 수 있는 점들이 모두 pop되어도 목적지에 아직 도착 못한 상태임으로, 벽을 두번 부수고 갈 수 있는 점들에게도 기회가 온다.

Plus

heapq에 벽을 부순 횟수와 좌표를 입력해줄 때는, 벽을 부순 횟수가 최소인 점들이 pop될 수 있게 해줘야한다. [벽을 부순 횟수, x, y]

heapq.heappush(point, [wall+1, ax, by])

CODE

import heapq as hq
from collections import deque
import sys
read = sys.stdin.readline

m, n = map(int, read().split())
maiz = list(list(read().strip()) for _ in range(n))
#해당 좌표까지 도달하는데 부숴야하는 벽의 최소 개수
check = list(list(-1 for _ in range(m)) for _ in range(n))
check[0][0] = 0

#첫 번째 값은 해당 좌표까지 부수면서 온 벽의 개수, 두세번째 값은 좌표를 나타낸다.
point = [[0, 0, 0]]
#벽을 최소로 부순 경우 우선적으로 탐색해나가기 위해 heapq를 사용해 최소값들 우선적으로 추출해 낸다.
hq.heapify(point)

dx = [1, 0, 0, -1]
dy = [0, 1, -1, 0]

while point:
    wall, a, b = hq.heappop(point)
    for x, y in zip(dx, dy):
        ax, by = a+x, b+y
        #이미 check에 값이 저장되어 있으면, 그 값이 최소로 부순 벽의 개수임으로 다시 탐색할 필요가 없다.
        if 0 <= ax < n and 0 <= by < m and check[ax][by] == -1:
            if maiz[ax][by] == '1':
                hq.heappush(point, [wall+1, ax, by])
                check[ax][by] = wall+1
            else:
                hq.heappush(point, [wall, ax, by])
                check[ax][by] = wall
print(check[-1][-1])

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]