최단경로 응용문제(이코테) - 1

날짜 : 2022. 12. 07

사용 언어 : python

 

문제

 

코드

import sys
import heapq

INF = int(1e9)
n, m, start = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]  # 각 노드에 대한 (도착점, 비용) 저장
distance = [INF] * (n + 1)  # 시작점 기준 노드별 최단거리

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))  # 시작노드로 가는 최단거리 : 0 / 큐에 삽입
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:  # 기존 시작점~now 까지의 거리가 dist보다 짧다면
            continue
        for i in graph[now]:  # 노드 now 기준으로 인접노드 확인
            cost = dist + i[1]  # (start->now 노드 거리) + (now 노드 + 인접노드)
            if cost < distance[i[0]]:
                distance[i[0]] = cost  # 해당 인접노드까지의 거리
                heapq.heappush(q, (cost, i[0]))


for _ in range(m):
    x, y, z = map(int, sys.stdin.readline().split())  # 시작, 도착, 비용
    graph[x].append((y, z))  # 노드 x 기준

dijkstra(start)

cnt = 0
max_dist = 0

for d in distance:
    if d != INF:
        cnt += 1
        max_dist = max(max_dist, d)

print(cnt-1, max_dist)  # 본인 노드는 제외
#print(graph)
#print(distance)

 

풀이

- n, m의 값이 각각 30,000, 200,000이기 때문에 값이 너무 커져 플로이드-워셜 알고리즘은 시간초과가 발생한다.

- 그렇기에 다익스트라 알고리즘을 활용하여 문제를 해결한다.

- 각 노드를 기준으로 edge에서 알 수 있는 시작점, 도착점과 비용을 입력받아 graph에 입력한다.

- 그 후에 다익스트라 알고리즘을 활용하여 start 노드 기준 각 노드간의 최소 도달 cost를 구한다.(distance 리스트)

- 그리고 distance 리스트(start ~ 각 노드)에서 INF가 아닌 원소의 개수(도달 가능한 경우)를 찾아 각 개수와 최댓값을 갱신한다.

- 마지막으로 개수에서 1을 뺀 후(start->start 제외)에 답을 출력한다.

 

 

알게된 점

- 

 

 

참고 사이트

- https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘

- 원본 강의 : https://youtu.be/acqm9mM1P6o