👉문제 링크

느낀점

• 간단했다.
• 다익스트라 문제를 풀어보았다.

정답 코드 및 해설

import heapq

d = [(0, 1), (1, 0), (-1, 0), (0, -1)]

tc = 0

while True:
    tc += 1
    world_size = int(input())
    if world_size == 0:
        break
    world_status = [list(map(int, input().split())) for _ in range(world_size)]
    world_available = [[1 for _ in range(world_size)] for __ in range(world_size)]
    world_available[0][0] = 0
    heap = [(world_status[0][0], 0, 0)]
    while heap:
        origin_score, origin_x, origin_y = heapq.heappop(heap)
        if origin_x == world_size - 1 and origin_y == world_size - 1:
            heap = []
            print("Problem {}: {}".format(tc, origin_score))
            break
        for direction in range(4):
            dx, dy = d[direction]
            new_x, new_y = origin_x + dx, origin_y + dy
            if 0 <= new_x < world_size and 0 <= new_y < world_size and world_available[new_y][new_x]:
                score = origin_score + world_status[new_y][new_x]
                world_available[new_y][new_x] = 0
                heapq.heappush(heap, (score, new_x, new_y))