[백준] 1261번-(Python 파이썬) - Dijkstra

문제링크 : https://www.acmicpc.net/problem/1261

이번문제는 미로탐색 문제와 매우 비슷하다.
조금 다른점은 가중치가 벽을 부순 횟수와 같은 것인다.
최단거리로 이동을 하면서 그 사이에 벽이 있을 시 벽을 부수는데 그 값을 더해주는 알고리즘을 구현해야한다.

넓이우선탐색, 깊이우선탐색 문제를 다양하게 풀어보고나서 이번 문제를 도전해보는게 좋을것이라는 생각이 들었다.
heapq를 이용하여 bfs로 구현하였다.

import sys
from heapq import heappush,heappop

input = sys.stdin.readline
m, n = map(int, input().split())
maze = []
visit =[[0] * m for _ in range(n)]

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

def bfs():
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    heap = []
    heappush(heap, [0, 0, 0])
    visit[0][0] = 1
    while heap:
        a, x, y = heappop(heap)
        if x == n - 1 and y == m - 1:
            print(a)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visit[nx][ny] == 0:
                if maze[nx][ny] == 1:
                    heappush(heap, [a+1, nx, ny])
                else:
                    heappush(heap, [a, nx, ny])
                visit[nx][ny] = 1

bfs()