문제

https://www.acmicpc.net/problem/4485

내 인생 스위치 게임 ㅠㅠ 참고로 왼쪽이 젤다공주 오른쪽이 링크입니다

이 문제를 읽어보면 [0,0]에서 시작해서 [n-1,n-1] 까지 최소금액만 잃고 가는 것이 목표인데 결국 [0,0]에서 시작해서 다른 모든 칸까지의 최소금액을 알아야한다! 즉, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘인 "다익스트라 알고리즘"을 사용해야한다.

내 코드

import sys ,heapq
INF=int(1e9)

dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]


def dijkstra(start, distance, n):
    q = []
    heapq.heappush(q, (graph[start][start], start, start))
    distance[start][start] = graph[start][start]

    while q:
        dist, start, end = heapq.heappop(q)
        if distance[start][end] < dist:
            continue
        tmp = []
        for x, y in zip(dx, dy):
            if -1 < start + x < n and -1 < end + y < n:
                tmp.append((start + x, end + y))

        for t in tmp:
            cost= dist + graph[t[0]][t[1]]
            if cost< distance[t[0]][t[1]]:
                distance[t[0]][t[1]]=cost
                heapq.heappush(q, (distance[t[0]][t[1]], t[0], t[1]))

def print_answer(ans):
    for i in range(len(ans)):
        print("Problem {0}: {1}".format(i+1,ans[i]))

ans=[]
while True:
    n=int(input())
    if n==0:
        break
    graph=[]
    distance=[[INF]*n for _ in range(n)]
    for _ in range(n):
        graph.append(list(map(int,sys.stdin.readline().strip().split())))

    dijkstra(0,distance,n)
    ans.append(distance[n-1][n-1])

print_answer(ans)

나는 기존에 다익스트라 알고리즘을 1차원 형태로만 연습했었는데 이 문제에서는 2차원 형태라는 점에서 차이가 있었다.

기존에 1차원 형태로 연습했을때는, 우선순위 큐에 값을 넣을 때 (가치,노드) 형태로 넣었는데 이번 문제에서는 (가치,출발노드,도착노드)형태로 넣었다.

또 dx=[1,-1,0,0] , dy=[0,0,-1,1] 를 이용해서 현재 위치를 기준으로 상하좌우 좌표값 중 유효한 좌표에 대해서만 탐색하도록 했다! (범위를 벗어나는 좌표는 취급 x)

이 부분들 외에는 기본적인 다익스트라 알고리즘과 거의 비슷하다..
그리고 출력 부분에서 format을 사용해서 원하는 형태로 출력되도록 했다!

막학기라 바빠서 닌텐도 할 시간도 없는데 코테에서나마 젤다를 볼 수 있어서 좋았다....😂