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

Jaden Kim·2022년 4월 28일
0

사용한 알고리즘/자료구조

각 칸을 지날 때 내야 할 비용이 주어진 상황에서, [0][0]에서 [N-1][N-1]로 가는 최소 비용 경로를 구하는 문제이다.

각 칸에서 상하좌우 방향으로 모두 이동할 수 있으므로, 각 방향으로 모두 엣지로 연결되어있다고 생각하고 다익스트라를 수행하면 된다.

처음에 시간 초과 때문에 틀린 것으로 나왔는데, if min_cost[nx][ny] <= new_cost 부분에서 =을 넣어주지 않아서 생긴 문제였다.

코드

from sys import stdin
import heapq

input = stdin.readline
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def dijkstra():
    q = []
    heapq.heappush(q, (graph[0][0], 0, 0))
    min_cost[0][0] = graph[0][0]
    while q:
        cost, x, y = heapq.heappop(q)
        if x == N-1 and y == N-1:
            return
        if min_cost[x][y] < cost:
            continue
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            new_cost = cost+graph[nx][ny]
            if min_cost[nx][ny] <= new_cost:
                continue
            min_cost[nx][ny] = new_cost
            heapq.heappush(q, (new_cost, nx, ny))


problem_idx = 1
answer = ""
while True:
    N = int(input())
    if N == 0 :
        break
    graph = [list(map(int, input().split())) for _ in range(N)]
    min_cost = [[INF]*N for _ in range(N)]
    dijkstra()
    answer += f'Problem {problem_idx}: {min_cost[N-1][N-1]}\n'
    problem_idx += 1

print(answer)

0개의 댓글