화성 탐사

📌문제

당신은 화성 탐사 기계를 개발하는 프로그래머다. 그런데 화성은 에너지 공급원을 찾기가 힘들다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 한다.

화성 탐사 기계가 존재하는 공간은 NxN크기의 2차원 공간이며 각각의 칸을 지나기 위한 비용이 존재한다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하시오.

 

📌풀이

NxN 크기의 맵이 주어졌을 때 맵의 각 칸을 노드로 보고 상하좌우로 모든 노드가 연결되어 있다고 생각

다익스트라 최단 경로 알고리즘 사용

 

📌코드

import heapq
import sys

input = sys.stdin.readline
INF = int(1e9)  # 무한

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

for tc in range(int(input())):
    n = int(input())

    graph = []
    for i in range(n):
        graph.append(list(map(int, input().split())))

    # 최단거리 테이블 무한으로 초기화
    distance = [[INF] * n for _ in range(n)]

    x, y = 0, 0  # 시작 위치 0,0
    # 시작 노드로 가기 위한 비용은 0,0 위치의 값으로 설정하여 큐에 삽입
    q = [(graph[x][y], x, y)]
    distance[x][y] = graph[x][y]

    # 다익스트라 알고리즘
    while q:
        # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
        dist, x, y = heapq.heappop(q)
        # 현재 노드가 이미 처리된적 있다면 무시
        if distance[x][y] < dist:
            continue
        # 현재 노드와 연결된 다른 인접 노드 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 맵의 범위 벗어나면 무시
            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            cost = dist + graph[nx][ny]
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[nx][ny]:
                distance[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny))

print(distance[n - 1][n - 1])

 

📌참고

https://g.co/kgs/eyd5SSd

이것이 취업을 위한 코딩 테스트다 with 파이썬