이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 그래프는 인접 행렬 방식으로 저장하였고 4가지 방향으로 너비우선탐색을 진행하며 방문 처리를 진행하였고 다익스트라 알고리즘을 통해 최소 비용을 구하였다.

• 출력 시 숫자를 표시하기 위한 변수 time을 0으로 선언한다.
• 무한 반복하는 while문을 돌린다.
  -> n을 입력받는다.
  -> 만약 n이 0이라면 while문을 종료한다.
  -> 그래프를 저장할 리스트 graph를 선언한다.
  -> n번 반복하는 for문을 돌린다.
  --> graph를 입력받는다.
  -> 4가지 방향에 대한 정보를 dy, dx에 짝지어 저장한다.
  -> 최대값을 INF 변수에 저장한다.
  -> 방문처리에 사용할 리스트 visited를 False n*n으로 채운다.
  -> 각 인덱스까지의 최소 비용을 저장할 리스트 results를 선언하고 INF n*n만큼 채운다.
  -> results[0][0]을 graph[0][0]로 갱신한다.
  -> 다익스트라에 사용할 큐 q를 최소힙으로 선언한다.
  -> q에 (graph[0][0], 0, 0)을 넣는다.
  -> q가 있을 동안 반복하는 while문을 돌린다.
  --> cost, y, x을 q에서 추출한다.
  --> visited[y][x]를 True로 갱신한다.
  --> 만약 cost가 results[y][x]보다 클 경우, 다음 반복으로 넘긴다.
  --> 4번 반복하는 i에 대한 for문을 돌린다.
  ---> ny에 y+dy[i]를 저장한다.
  ---> nx에 x+dx[i]를 저장한다.
  ---> 만약 ny, nx가 0보다 크거나 같고, ny, nx가 n보다 작고, visited[ny][nx]가 False일 경우,
  ----> nxt_cost를 cost+graph[ny][nx]를 저장한다.
  ----> 만약 results[ny][nx]가 nxt_cost보다 클 경우,
  -----> results[ny][nx]를 nxt_cost로 갱신한다.
  -----> q에 (nxt_cost, ny, nx)를 넣는다.
  -> time을 1 증가시킨다.
  -> Problem %(time): %(results[n-1][n-1]을 출력한다.

Code

import heapq
import sys
time=0
while True:
    n=int(input())
    if n==0:
        break
    graph=[]
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    dy=[0, 0, -1, 1]
    dx=[-1, 1, 0, 0]
    INF=sys.maxsize
    visited=[[False]*n for _ in range(n)]
    results=[[INF]*n for _ in range(n)]
    results[0][0]=graph[0][0]
    q=[]
    heapq.heappush(q, (graph[0][0], 0, 0))
    while q:
        cost, y, x=heapq.heappop(q)
        visited[y][x]=True
        if cost>results[y][x]:
            continue
        for i in range(4):
            ny=y+dy[i]
            nx=x+dx[i]
            if ny>=0 and nx>=0 and ny<n and nx<n and not visited[ny][nx]:
                nxt_cost=cost+graph[ny][nx]
                if results[ny][nx]>nxt_cost:
                    results[ny][nx]=nxt_cost
                    heapq.heappush(q, (nxt_cost, ny, nx))
    time+=1
    print('Problem %d: %d' %(time, results[n-1][n-1]))