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

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

이번 문제도 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있다.
사실상 스토리만 다르고 1261번이랑 거의 같은 문제이다.

백준-1261번 풀이
여기에 자세한 설명은 해두었으니 참고하면 될 것 같다.

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
n = int(input())
room = []
for _ in range(n):
    room.append(list(map(int, input().rstrip())))
visit = [[0] * n for _ in range(n)]

def dijkstra():
    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 == n - 1:
            print(a)
            return
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == 0:
                visit[nx][ny] = 1
                if room[nx][ny] == 0:
                    heappush(heap, [a + 1, nx, ny])
                else:
                    heappush(heap, [a, nx, ny])

dijkstra()