화성 탐사 ACM-ICPC 최단거리

화성 탐사 기계는 에너지를 효율적으로 사용하기 위해 최적의 경로를 찾아야 합니다.

기계가 존재하는 공간은 NxN 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용이 존재합니다. 가장 왼쪽 위 칸인 [0][0]위치에서 가장 오른쪽 아래 [N-1][N-1] 위치로 이동하는 최소 비용을 출력하세요 이동가능한 방향은 상하좌우 인접한방향입니다.

예시 3 5 5 4 3 9 1 3 2 7 정답 : 20

플로이드 워셜 알고리즘을 충분히 학습했으니 이정도는 굉장히 쉽게 풀 수 있습니다. (라고 생각했습니다)

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

입력을 받고 맵 리스트를 초기화 해줍시다.

결국 정답은 마지막까지 갈때의 최단 거리인데(그것도 상하좌우로만) 한칸씩 이동하면서 해당 값만 갱신하면서 나가면 됩니다.

sum_temp_1 = 0
sum_temp_2 = 0
for i in range(n):
    sum_temp_1 += map_list[i][0]
    map_list[i][0] = sum_temp_1
    sum_temp_2 += map_list[0][i]
    map_list[0][i] = sum_temp_2

인덱스 때문에 row와 column의 첫번째는 더해주면서 초기화를 해주고 2번째 열부터 쭉 비교를 해줍시다.

for a in range(1,n):
    for b in range(1,n):
        map_list[a][b]+=min(map_list[a][b-1],map_list[a-1][b])
        
print(map_list[n-1][n-1])

내 위치에서 위와 왼쪽에서 가장 작은 값을 더해나가면 마지막까지 도달했을때 최소 거리를 구할 수 있습니다.

라고 생각했는데

5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5

이렇게 생긴 테스트 케이스를 통과하지 못했습니다. 보시면 3 - 1 - 2 - 1 - 0 -2 - 0 - 1 … 순으로 빙돌아가면 최소값 19가 나오는데 저는 이런 경우를 생각하지 않았기 때문에 통과를 못했습니다.

거기에 NxN크기가 125로 제한되었지만 2차원 공간을 플로이드 워셜 알고리즘을 사용할 경우 10,000을 훌쩍 넘을 수가 있습니다. 따라서 다익스트라 최단 경로 알고리즘을 사용해서 문제를 풀어야 합니다.

import heapq
INF = int(1e9) #무한을 의미하는 값으로 10억을 설정

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

'''
#전체 테스트 케이스(Test Case)만큼 반복
for tc in range(int(input())):
    #노드의 개수를 입력받기
    n = list(map(int,inpust().split()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]

다익스트라 알고리즘을 사용하기 위해서 heap를 이용합니다.

테이블의 입력을 받고 거리를 구하기 위한 최단거리 테이블을 초기화 해줍시다. 이제 큐를 이용하여 노드로 가기 위한 비용 관리를 해줍시다.

첫번째 위치의 비용과 가는 비용은 동일합니다.

#다익스트라 알고리즘 수행
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])

다익스트라 알고리즘을 수행을 합시다.

우리가 지금 들어 있는 큐에서 노드를 꺼내고 현재 노드가 이미 처리된 적이 있다면 conitnue로 무시를 하고 아니라면 인접한 4방향(상하좌우)노드를 확인을 합니다. 그리고 거리가 벗어나지 않았을 경우에 현재비용+앞으로 갈 위치의 비용을 갱신을 해줍니다. 그래서 현재의 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 비용을 갱신을 해주고 집어넣어 줍니다. 이렇게 모든 가능한 노드를 순회를 하게 됩니다.