[이코테] 최단경로연습03. 화성 탐사

[이코테] 최단경로연습03. 화성 탐사

Level 2

문제 링크(페이지) : 이코테 388p

당신은 화성 탐사 기계를 개발하는 프로그래머이다.

에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다.

NxN 크기의 2차원 공간에 화성 탐사 기계가 존재하고, 각각의 칸을 지나기 위한 비용이 존재한다.

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성해라.

문제 풀이

문제에서 특정한 위치에서 특정 위치로 이동하는 최단 경로를 구하라고 했으므로, 다익스트라 알고리즘을 이용하는 것이 적합하다.

구현 연습에서 풀었던 것 처럼 상, 하, 좌, 우를 확인해 이동하고 범위 내에 있을 경우 최단거리를 저장한다.

코드

import heapq t = int(input()) INF = int(1e9) mx = [-1, 1, 0, 0] my = [0, 0, -1, 1] for _ in range(t): n = int(input()) distance = [[INF] * n for _ in range(n)] cost = [] for _ in range(n): cost.append(list(map(int, input().split()))) x, y = 0, 0 # 비용과 좌표를 큐에 삽입 q = [(cost[x][y], x, y)] distance[x][y] = cost[x][y] while q: # 가장 가까운 노드를 빼옴 c, a, b = heapq.heappop(q) if distance[a][b] >= c: continue for i in range(4): nx = a + mx[i] ny = b + my[i] if 0 <= nx < n and 0 <= ny < n: c_ = c + cost[nx][ny] # 최단 거리이면 저장하고 큐에 삽입 if distance[nx][ny] > c_: distance[nx][ny] = c_ heapq.heappush(q, (c_, nx, ny)) print(distance[n-1][n-1])

from http://shotory.tistory.com/56 by ccl(A) rewrite - 2021-12-30 01:27:07