태야

<내 코드>

import heapq
import sys


def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    while(q):

        cnt, x, y = heapq.heappop(q)  # (0,0,0)형식
        done[x][y] = 1

        if x == N-1 and y == M-1:
            return cnt

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if (0 <= nx < N) and (0 <= ny < M) and done[nx][ny] == 0:
                done[nx][ny] = 1

                # 길이 있는 경우 우선순위(최소힙)가 가도록 한다.
                if maps[nx][ny] == '0':
                    heapq.heappush(q, (cnt, nx, ny))
                elif maps[nx][ny] == '1':
                    heapq.heappush(q, (cnt+1, nx, ny))
                


M, N = map(int, sys.stdin.readline().split())
maps = [list(str(sys.stdin.readline())) for _ in range(N)]
q = []
done = [[0]*M for _ in range(N)]

heapq.heappush(q, (0, 0, 0))

print(bfs())

BFS와 우선수위 큐를 이용하는 독특한 문제이다. 처음에는 BFS로만 문제를 풀려고 했지만 어려웠다.

heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 있는 채로 BFS를 해야하기 때문이다.

여기서 길(0)이 있다면 우선순위를 줘서 그 길부터 가도록 한다. 만약 길이 없고 벽(1)만 있다면 cnt+1을 해줘 벽을 부순다. 우선순위가 낮은 값부터 탐색하게 되서 원하는 동작이 구현된다.