https://www.acmicpc.net/problem/2665
- 다익스트라 이용
- 문제에서는 흰색(지나갈 수 있는 곳)을 1, 검은색을 0으로 해줬는데 입력받은 뒤 이를 완전히 뒤집고 다익스트라 알고리즘을 통해 (N,N)으로 갈 수 있는 최단거리를 구해주면 끝
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
rooms = []
n = int(input())
distance = [[INF] * n for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(n):
strarr = input().strip()
room = [(int(ch) ^ 1) for ch in strarr]
rooms.append(room)
def dijkstra(start):
x, y = start
q = []
heapq.heappush(q, (0, start))
distance[x][y] = 0
while q:
dist, now = heapq.heappop(q)
x, y = now
if distance[x][y] < dist:
continue
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
cost = dist + rooms[nx][ny]
if cost < distance[nx][ny]:
distance[nx][ny] = cost
heapq.heappush(q, (cost, (nx, ny)))
dijkstra((0,0))
print(distance[n-1][n-1])728x90
