1/15 Coding Test

✅ Coding Test

오늘 풀이할 문제는 그래프 구현 문제

🎈 1753 최단경로

방향 그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 만들기. (모든 간선의 가중치는 10이하의 자연수다.)

첫 줄에 정점 개수 V, 간선 개수 E가 주어지고 모든 정점에는 1부터 ~ V까지 번호가 매겨져 있다.
둘째 줄에는 시작 정점 번호가 주어지고 셋째 줄부터 E줄에 걸쳐 각 간선을 나타내는 3개의 정수가 순서대로 주어진다.
이는 U->V로 이동하면서 가중치가 W인 간선이 존재한다는 뜻이고 서로 다른 두 정점 사이엔 여러 개의 간선이 존재할 수도 있다.

첫 줄부터 V줄에 걸쳐 i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다.
시작점은 0으로, 경로가 존재하지 않는 경우에는 INF를 출력한다.

import sys, heapq
input = sys.stdin.readline

node, edge = map(int, input().split())
start = int(input())
graph = [[] for _ in range(node+1)]
for i in range(edge):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))

heap = []
INF = int(1e9)
distance = [INF] * (node + 1)

def dijkstra(start):
    distance[start] = 0
    heapq.heappush(heap, (0, start))
    while heap:
        now_dist, now_node = heapq.heappop(heap)
        for next_node, dist in graph[now_node]:
            if distance[next_node] > now_dist + dist:
                distance[next_node] = now_dist + dist
                heapq.heappush(heap, (now_dist + dist, next_node))

dijkstra(start)

for i in distance[1:]:
    if i == 1e9:
        print('INF')
    else:
        print(i)

< 코드 해설 >

음의 가중치가 없으므로 시작 노드부터 모든 노드를 탐색하는 다익스트라 알고리즘으로 구현한 문제

우선순위 큐를 활용하고 시작노드부터 모든 노드까지의 거리를 나타내는 distance 배열을 무한대로 두고 최솟값으로 갱신해가며 탐색을 시작한다.
구체적인 로직은 다음과 같다.

1. distance 배열에 현 위치를 0으로 두고 힙에 (거리, 지점) 순서대로 입력한다. (지점, 거리)순서대로 입력하면 거리를 최소화하는게 아니라서 시간 초과 발생.
2. 힙이 빌 때까지 아래 로직을 반복한다.
   2-1. 현재 힙에서 거리, 지점을 빼고 그래프 상 인접 노드와 비교 진행
   2-2. 만일 현 지점까지의 거리 + 다음 지점 이동 거리가 무한대보다 작다면 distance 배열 갱신하고 힙에 넣어주기
3. 결과적으로 distance 배열을 1번 인덱스부터 끝까지 출력하되 1e9로 표현된다면 INF를, 아닌 경우 해당 i번 노드까지의 최단 경로를 출력한다.