[백준] 4485번, 녹색 옷 입은 애가 젤다지?

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

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

 

이름이 젤다길래 풀어봤는데 젤다는 안나오고 뭔 강도가...

 

 

문제

젤다가 (0, 0)의 위치에서 (N - 1, N - 1) 위치로 이동하는데

맵에는 강도가 있어서 강도가 있는 위치로 지나가면 일정 금액을 뜯긴다....

그래서 최대한 덜 뜯기고 갔을 때, 잃은 돈을 출력해주기

 

 

풀이

다익스트라의 정석같은 문제였음..

맵과 같은 크기의 리스트를 만든 후, 엄청 큰 값(inf)을 넣어둠

처음 출발점부터 BFS같이 맵을 탐색하는데,

visited 대신 아까 만든 리스트에 내가 계산한 지금까지 뜯긴 돈을 넣어준다

단, BFS와 다르게

• 힙을 이용하고,
• 힙에서 꺼낸 현재 뜯긴 돈이 저장된 값보다 크다면 그냥 빼주고,
• 계산해서 나온 뜯긴 돈이 저장된 값보다 크다면 힙에 넣어주지 않음

힙을 이용해서 최대한 작은 돈부터 계산할 수 있다!

 

import heapq

# 상하좌우로 이동
dire = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def gangdo():
    pq = []
    heapq.heappush(pq,(MAP[0][0], 0, 0))
    while pq:
        # lose는 지금까지 잃은 돈
        lose, cy, cx = heapq.heappop(pq)
        
        # 만약 지금까지 잃은 돈이, 여기서 구했던 최소값보다 크다면
        if lose > coin[cy][cx]:
            continue	# 계산할 필요가 없음

        for dy, dx in dire:
            ny, nx = cy + dy, cx + dx
            if 0 <= ny < N and 0 <= nx < N:
                nextlose = lose + MAP[ny][nx]
                # 다음 값을 계산했을 때, 이미 저장된거보다 작으면 넣고 아님 ㄴㄴ
                if coin[ny][nx] > nextlose:
                    coin[ny][nx] = nextlose
                    heapq.heappush(pq,(nextlose, ny, nx))

tc = 0
while True:
    tc += 1
    N = int(input())
    # N이 0이 되면 프로그램 종료
    if not N:
        exit()
    MAP = [list(map(int,input().split())) for _ in range(N)]
    
    # 각 위치에서 잃는 최소한의 coin
    coin = [[float('inf') for _ in range(N)] for _ in range(N)]
    gangdo()
    print(f'Problem {tc}: {coin[N-1][N-1]}')

 

---

다익스트라 잘만 쓰면 참 좋은 것 같다

예전에 풀었던 BFS / DFS 문제들도 이런식으로 풀 수 있을려나