https://www.acmicpc.net/problem/4485
import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline
result = []
while True:
n = int(input())
if n == 0:
break
graph = []
for i in range(n):
graph.append(list(map(int, input().split())))
def dijkstra():
heap = []
distance = []
for i in range(n):
distance.append([INF] * n)
dRow = [0, 0, 1, -1]
dColumn = [1, -1, 0, 0]
heapq.heappush(heap, [graph[0][0], 0, 0])
while heap:
dist, row, column = heapq.heappop(heap)
if distance[row][column] < dist:
continue
for i in range(4):
movedRow, movedColumn = row + dRow[i], column + dColumn[i]
if movedRow < 0 or n <= movedRow or movedColumn < 0 or n <= movedColumn:
continue
cost = dist + graph[movedRow][movedColumn]
if cost < distance[movedRow][movedColumn]:
distance[movedRow][movedColumn] = cost
heapq.heappush(heap, [cost, movedRow, movedColumn])
return distance
result.append(dijkstra()[n-1][n-1])
for i in range(len(result)):
print(f'Problem {i+1}: {result[i]}')
이 문제는 다익스트라 알고리즘과 이코테의 2차원 평면 기술을 통해서 쉽게 해결 가능하다
파라미터를 입력받고 다익스트라 메소드 부분에서 dRow와 dColumn을 정의한다
그리고 row, column에서 동서남북으로 이동시 범위를 벗어나지 않는다면 다익스트라 알고리즘을 수행할 수 있게 heap에 넣는다