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

문제

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

[4485번: 녹색 옷 입은 애가 젤다지?

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주

www.acmicpc.net](https://www.acmicpc.net/problem/4485)

문제해결방법

• 다익스트라 알고리즘을 최소힙 자료구조를 이용해서 해결했다.
• (0,0)에서 (n-1,n-1)로 최소 루피를 잃으면서 이동해야하는 문제다.
• 매번 최소 소비 루피장소를 선택하려면 최소힙 자료구조를 사용해야한다. 현재까지 잃은 루피에서 그 다음 이동장소(현재위치에서 상하좌우인접 장소)에서 잃게될 루피를 힙자료구조에 넣는다.(다음행까지 잃은 루피 누적합,다음 행,다음 열)
• 파이썬의 최소힙은 첫번째 요소를 기준으로 최소힙으로 정렬된다.
• 그리고 최소힙이 빌때 까지 꺼내면서 꺼내진 곳의 위치가 (n-1,n-1)이라면 이때 현재까지 잃은 루피누적합을 출력하면 된다.
• 이때 주의할 점은 힙큐에 넣을때 방문처리를 해주는 것이다. 방문처리를 하지않으면 방문했던 곳이 다시 힙큐에 넣어질 수 있다. 그리고 이렇게 넣어질 때의 값이 0으로 더해진 누적루피라면 기존 힙큐에 있던 값보다 작아져서 계속 같은 장소의 값이이 힙큐에서 꺼내지면서 무한루프에 빠지게 된다. 위의 문제에서는 3번째 테스트케이스가 그 예이다.

코드

import sys
import heapq
from collections import deque

def dijkstra():
    global visited
    q = []
    heapq.heappush(q,(graph[0][0],0,0))
    visited[0][0] = True

    while q:
        now_rupy, now_r,now_c = heapq.heappop(q)

        if now_r == n-1 and now_c == n-1:
            return now_rupy

        for dir in range(4):
            next_r = now_r + dir_r[dir]
            next_c = now_c + dir_c[dir]

            if next_r>=0 and next_r<n and next_c>=0 and next_c<n:
                if not visited[next_r][next_c]:
                    visited[next_r][next_c] = True
                    heapq.heappush(q,(now_rupy + graph[next_r][next_c],next_r,next_c))


input = sys.stdin.readline
dir_r = [-1,1,0,0]
dir_c = [0,0,-1,1]
cnt = 0
while True:
    cnt += 1
    n = int(input())
    graph = []
    visited = [[False]*n for _ in range(n)]
    if n == 0:
        break
    else:
        for _ in range(n):
            graph.append(list( map(int,input().split())))
        answer = dijkstra()
        print(f"Problem {cnt}: {answer}")