백준 4485 : 녹색 옷 입은 애가 젤다지? (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline
dx=[-1,1,0,0]
dy=[0,0,-1,1]
INF=int(1e9) ; i = 1


def Dijkstra():

    heap=[] ; heapq.heappush(heap,(graph[0][0] , 0 , 0))

    dp=[ [INF]*(N+1) for _ in range(N+1) ]
    dp[0][0]=0

    while heap:

        value,x,y=heapq.heappop(heap)

        if dp[x][y]+graph[x][y]<value: # 처음에 시작점 값을 추가해줬으므로 dp와 graph 값을 함께 더한다.
            continue

        for i in range(4):

            nx=x+dx[i] ; ny=y+dy[i]

            if 0<=nx<N and 0<=ny<N:

                if value+graph[nx][ny]<dp[nx][ny]:
                    dp[nx][ny]=graph[nx][ny]+value
                    heapq.heappush(heap , (graph[nx][ny]+value , nx , ny))




    return dp[N-1][N-1]

while True:

    N=int(input())


    if N==0:
        break

    graph=[ list(map(int,input().split())) for _ in range(N) ]

    Answer=Dijkstra()
    print("Problem %d: %d"%(i , Answer))

    i+=1

📌 어떻게 접근할 것인가?

다익스트라 기초 문제입니다. graph 를 입력받고 $(0,0)$ 부터 시작해서 $(N-1,N-1)$ 로 가는 최단경로를 구해주면 됩니다.

다익스트라를 그대로 구현해주면 되는데 주의해줘야 할점은 처음 시작점은 graph[0][0] 값을 가지고 시작하기 때문에 값을 체크할때 dp 의 값과 graph 값의 합이 value 보다 작다면 그때 continue 를 실행해줍니다.