최단 거리 알고리즘

• 다익스트라 알고리즘
  그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
• 플로이드 워셜 알고리즘
  모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우
• 벨만 포드 알고리즘

✅ 문제

메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치도어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C
둘째 줄부터 M + 1번째 줄에 걸쳐서 통로에 대한 정보 X(특정 도시), Y(다른 특정 도시), Z(메시지가 전달되는 시간)

입력 예시

3 2 1
1 2 4
1 3 2

출력 예시

2 4

💻 코드

import sys
import heapq

input = sys.stdin.readline

INF = int(1e9)

N, M, C = map(int, input().split())

# 노드에 연결되어 있는 정보를 담는 2차원 그래프 리스트 
graph = [[] for _ in range(N + 1)]

for _ in range(M):
    X, Y, Z = map(int, input().split())
    graph[X].append((Y, Z))

# 최단 거리 테이블
distance = [INF] * (N + 1)

def dijkstra(start):
    # 큐
    q = []
    heapq.heappush(q,(0, start))
    distance[start] = 0
 
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(C)

count = 0
time = 0
for i in range(1, len(distance)):
    if distance[i] > 0 and distance[i] < INF:
        count += 1
        temp = distance[i]
        time = max(time, temp)
print(count, end = " ")
print(time)

설계

다익스트라 알고리즘으로 문제를 해결하였다. distance 테이블에서 방문한 도시와 시간 정보를 가져왔다.

📝 정리

우선순위 큐를 사용한 다익스트라 알고리즘 잊어버리지 않기