[BaekJoon] 백준 1261번: 알고스팟

1261번 : 알고스팟

한 노드에서 모든 노드의 최단거리를 구할 수 있는 다익스트라를 사용하면 된다.

벽을 부수고 도착한 경우 거리를 1 늘려주면 된다.

즉, 도착 노드가 1인 간선의 무게는 1로, 도착 노드의가 0인 간선의 무게는 0으로 두고 문제를 풀면 된다.

---

import heapq


def solution():
    dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    break_wall_cnt = [[float('inf') for _ in range(M)] for _ in range(N)]
    break_wall_cnt[0][0] = 0
    queue = []
    heapq.heappush(queue, (0, 0, 0))

    while queue:
        wall, now_i, now_j = heapq.heappop(queue)
        if break_wall_cnt[now_i][now_j] < wall:
            continue

        for value in dirs:
            cost, visit_i, visit_j = wall, now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < M:
                if field[visit_i][visit_j] == 1:
                    cost += 1

                if cost < break_wall_cnt[visit_i][visit_j]:
                    break_wall_cnt[visit_i][visit_j] = cost
                    heapq.heappush(queue, (cost, visit_i, visit_j))

    return break_wall_cnt[N - 1][M - 1]


if __name__ == "__main__":
    M, N = map(int, input().split())
    field = [list(map(int, input())) for _ in range(N)]
    print(solution())