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

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

문제를 쭉 읽어보면 A 노드에서 B 노드까지의 최단거리를 구하는 문제이다.

모든 노드 사이의 최단거리를 구하려면 플로이드를, 이렇게 특정 노드에 대한 최단거리를 구하고 싶다면 다익스트라를 사용하자.

다익스트라를 풀 땐 연결된 노드의 간선정보를 이용해 탐색을 했는데 이처럼 상하좌우로 탐색을 하는건 처음이라 헷갈렸다.

여담이지만 이 문제는 출력을 Problem 숫자: 답 으로 해야했다.

이럴때 굳이 자료형을 바꾸어 주지말고 print(f”{}”) 를 사용하면 자료형 변환 없이 바로 출력 할 수 있다.

---

import sys
import heapq


def solution():
    dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    distance = [[float('inf') for _ in range(N)] for _ in range(N)]
    distance[0][0] = field[0][0]
    queue = []
    heapq.heappush(queue, (distance[0][0], 0, 0))

    while queue:
        now_cost, now_i, now_j = heapq.heappop(queue)
        if now_cost < distance[now_i][now_j]:
            continue

        for value in dirs:
            visit_i, visit_j = now_i + value[0], now_j + value[1]
            if 0 <= visit_i < N and 0 <= visit_j < N:
                visit_cost = field[visit_i][visit_j]
                if now_cost + visit_cost < distance[visit_i][visit_j]:
                    distance[visit_i][visit_j] = now_cost + visit_cost
                    heapq.heappush(queue, (distance[visit_i][visit_j], visit_i, visit_j))

    return distance[N - 1][N - 1]


if __name__ == "__main__":
    num = 1

    while True:
        N = int(input())
        if not N:
            break
        field = [list(map(int, sys.stdin.readline().rsplit())) for _ in range(N)]

        print(f"Problem {num}: {solution()}")
        num += 1