[최단경로] 화성탐사

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

- 상, 하, 좌, 우로 탐색할 수 있는 화성 로봇이 있는데 (0, 0)지점부터 (n-1, n-1)까지 갈 때의 최단 경로를 구하기

2. 접근 방식

- 처음에는 플로이드 워셜 알고리즘을 활용하려고 했는데, 생각해보니 시간이 너무 오래걸릴 거 같았다. 그래서 다익스트라 알고리즘을 활용하기로 했다.

- 다익스트라 알고리즘의 경우 그래프에서 입력을 받아 이를 하나씩 꺼내면서 진행된다. 해당 문제의 경우 특정 노드를 기준으로 그래프에서 상, 하, 좌, 우에 해당하는 부분에 방문해서 비용을 계산하는 방식으로 코드가 알고리즘이 진행된다. 

3. 코드

import heapq

t = int(input())
INF = int(1e9)
#     북 동 남 서
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

for _ in range(t):
    n = int(input())
    graph = []
    for i in range(n):
        graph.append(list(map(int, input().split())))
    x, y = 0, 0 # (시작 위치 초기화)
    distance = [[INF]*n for _ in range(n)]
    q = [(graph[x][y], 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])

4. 코멘트

- 다익스트라를 활용하는데, 코스트 순으로 넣는게 아니라 기준 원소에서 시작해서, 상하좌우 위치를 확인해서 일단 넣고 생각한다. 그리고 상, 하, 좌, 우 중 거리가 가장 짧은 게 기록으로 남겨지도록 한다.

- 해당 문제의 경우 기존에 다익스트라 알고리즘의 형태만 기억하고 있어서 이를 활용할 그림이 안 나왔었다. 이런 방식으로도 알고리즘을 활용할 수 있음을 깨달은 문제였다.