[백준][Python] 1261 알고스팟

벽을 뚫는다 = 이동시 비용이 든다. = 가중치 있는 그래프

가중치가 0 과 1로 이루어진 그래프 탐색으로 맨앞 요소에 가중치 누적요소 cnt를 넣어 가중치가 낮은 길로 target을 찾아가는 bfs를 그리면 된다. 

heap을 이용해 낮은가중치탐색을 하는방법과

deque을 이용해 가중치가0인 노드이동에 대해 appendleft를 해주는 방법도 있다.

여튼 먼저 탐색해준다는게 핵심.

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

m, n = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
maze = []
visited = [[0] * m for i in range(n)]

for i in range(n):
    maze.append(list(map(int, input())))

def bfs(cnt,start_x,start_y):
    heap = []
    heappush(heap, [cnt, start_x, start_y])
    visited[0][0] = 1
    while heap:
        cnt, x, y = heappop(heap)
        if x == n - 1 and y == m - 1:
            print(cnt)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 사방탐색 후 방문안한곳 들어가고 벽이면 부순횟수 +1 아니면 그대로. 가중치가 작은좌표부터 탐색한다.
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == 0:
                heappush(heap, [cnt + 1 if maze[nx][ny] == 1 else cnt, nx, ny])
                visited[nx][ny] = 1
bfs(0,0,0)