녹색 옷 입은 애가 젤다지?

백준 4485

BFS는 갈 수 있는 곳과 갈 수 없는 곳으로 나뉘어 있다면, 다익스트라는 모두 갈 수 있는데 비용이 적게 들고 우선순위가 큰 곳을 방문한다는 차이가 있다.
따라서 다익스트라는 우선순위 큐를 떠올리는 것이 당연한 것이다.

import heapq

def bfs(i, j, t, maps):
    dp = [[1e9]*t for _ in range(t)]
    dp[i][j] = maps[i][j]
    q = []
    heapq.heappush(q, (maps[i][j], i, j))

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

    while q:
        w, x, y = heapq.heappop(q)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<t and 0<=ny<t:
                nw = w + maps[nx][ny]
                if nw < dp[nx][ny]:
                    dp[nx][ny] = nw
                    heapq.heappush(q, (nw, nx, ny))

    return dp[t-1][t-1]
                
cnt = 0
while True:
    t = int(input())
    if t==0:
        break
    cnt += 1
    maps = [list(map(int, input().split())) for _ in range(t)]
    print("Problem {}: {}".format(cnt, bfs(0,0,t, maps)))
    

맵에서 가중치는 도둑루피를 나타내고, 이 도둑루피가 최대한 적도록 지나가야한다. 길은 상하좌우 지나갈 수 있다.

다익스트라를 구현하기 위해서는 힙 모듈이 필요하고, 각 지점마다의 값을 계산한 dp테이블이 필요하다. 이 때 처음 dp테이블은 1e9로 초기화해둔다.

힙에 푸시할 때는 가중치를 기준으로 최소힙을 만들기 위해 (가중치, x좌표, y좌표) 순으로 넣는다.

각 좌표에서 상하좌우의 좌표가 범위내에 있고, 현재까지의 가중치(dp테이블) + 이웃의 가중치가 이웃까지의 가중치(dp테이블)보다 작다면 갱신해주고 힙에 넣는다.

이렇게 힙이 존재할때까지 반복해주고 마지막에 마지막행, 마지막 열의 가중치를 반환해주면 된다.