[BOJ] Q4485 녹색 옷 입은 애가 젤다지?

[BOJ] Q4485 녹색 옷 입은 애가 젤다지?

Question

Language: Python

Difficulty: Gold 4

해당 문제는 출발지로부터 목적지까지 잇는 가장 짧은 경로를 구하는 SSSP 유형의 문제이다. 다른 graph와 달리 2차원 좌표평면 상에서 동작하는 SSSP 문제로 dijkstra + 2-level array을 활용해서 풀이를 진행한다.

Solution

from heapq import heappush,heappop
from math import inf

def solution():
    count=0
    heap=[(graph[0][0],0,0)]
    distances[0][0]=graph[0][0]

    while heap:
        cost,row,col=heappop(heap)

        if cost > distances[row][col]:
            continue

        for dir in range(4):
            next_row=row+dy[dir]
            next_col=col+dx[dir]

            if next_row < 0 or next_row>=n or next_col < 0 or next_col>=n:
                continue

            new_distance=cost+graph[next_row][next_col]

            if new_distance < distances[next_row][next_col]:
                distances[next_row][next_col]=new_distance
                heappush(heap,(new_distance,next_row,next_col))
    
    return distances[n-1][n-1]

if __name__ == "__main__":
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    index=0
    while True:
        n=int(input())

        #n==0 이면 반복을 종료한다. 
        if n==0:
            break
        index+=1       
        graph=[list(map(int, input().split())) for _ in range(n)]
        distances=[[inf] * n for _ in range(n)]
        print(f"Problem {index}: {solution()}")