백준 4485: 녹색 옷 입은 애가 젤다지?(파이썬)

💡 2차원 맵에서의 최소 비용 경로: Dijkstra 알고리즘 구현

🧠 문제 배경

N×N 크기의 맵이 주어진다.
각 칸에는 비용이 있으며, 우리는 (0, 0)에서 시작해 (N-1, N-1)로 이동하고자 한다.
이동은 상하좌우로만 가능하고, 각 칸을 지날 때는 해당 칸의 비용을 지불해야 한다.

✅ 목표: (0, 0)에서 (N-1, N-1)까지의 최소 비용을 구하라

🔍 기본 구현: Dijkstra with 우선순위 큐

import sys
import heapq

sys.stdin = open('input.txt', 'r')

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

def dijkstra():
    heap = []
    heapq.heappush(heap, (arr[0][0], 0, 0))
    while heap:
        cost, x, y = heapq.heappop(heap)
        if x == N-1 and y == N-1:
            return cost

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx < 0 or ny < 0 or nx >= N or ny >= N:
                continue
            new_cost = cost + arr[nx][ny]
            if visited[nx][ny] <= new_cost:
                continue
            visited[nx][ny] = new_cost
            heapq.heappush(heap, (new_cost, nx, ny))

count = 0
while True:
    count += 1
    N = int(input())
    if N == 0:
        break
    arr = [list(map(int, input().split())) for _ in range(N)]
    visited = [[float('inf')] * N for _ in range(N)]
    result = dijkstra()
    print(f"Problem {count}: {result}")

❗ 내가 겪은 문제: 조건 하나로 인한 시간 초과

기존 코드:

if visited[nx][ny] <= new_cost:
    continue

문제점:

• new_cost == visited[nx][ny]일 때도 continue 처리됨 → 경로 누락 → 시간초과 가능

해결:

if visited[nx][ny] > new_cost:
    visited[nx][ny] = new_cost
    heapq.heappush(heap, (new_cost, nx, ny))

✅ 정리

• Dijkstra에서 조건 하나(<= vs >)가 성능과 정답을 좌우할 수 있다.
• 파이썬의 int는 자동으로 큰 정수도 처리하므로 오버플로우 걱정 없음
• 시간 제한이 있는 문제에서는 작은 조건 실수가 전체 실행시간을 좌우할 수 있다