[ 1261 ] [ Dijkstra ] 알고스팟

https://www.acmicpc.net/problem/1261

1261번: 알고스팟

 

풀이 과정

---

1. 다른때와 다르게, 최단 경로를 저장하는 distance를 2차원 배열로 지정해주어야 해서 특이한 경험이었음.
2. [0, 0]에서 시작하여 현재 이동할 수 있는 좌표 중 가장 최소로 벽을 부수어야 하는 좌표로 먼저 이동하여 갱신한다.
   • 상,하,좌,우로 이동하면서 거리 갱신이 가능한 경우 최소 히프에 넣어주는 방식으로 구현
   • 벽이 있는 경우는 1을 더해주고, 벽이 없는 경우는 0을 더해주는데, 그냥 입력 배열에 저장되어있는 값을 더해준다.
3. 마지막에, distance[N-1][M-1]을 출력해준다.
4. 원래 이런 문제는 BFS로만 풀었었는데 다익스트라 알고리즘으로도 풀리네..  BFS로 풀면 중복이 훨씬 많이 일어나서 비효율적이긴 할듯.

---

소스 코드

---

import sys
import heapq

input = lambda: sys.stdin.readline().rstrip()

M, N = map(int, input().split())

matrix = [list(map(int, list(input()))) for _ in range(N)]
distance = [[int(10e9)] * M for _ in range(N)]
distance[0][0] = 0

heap = []
heapq.heappush(heap, [0, 0, 0])

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

while heap:
    dist, x, y = heapq.heappop(heap)
    if distance[x][y] != dist:
        continue

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx and nx < N and 0 <= ny and ny < M:
            if distance[nx][ny] > dist + matrix[nx][ny]:
                distance[nx][ny] = dist + matrix[nx][ny]
                heapq.heappush(heap, [distance[nx][ny], nx, ny])


print(distance[N-1][M-1])