[최단경로] 전보

1. 문제 설명

도시와 도시가 연결되어 있을 때 전보를 보내는 경우 얼마나 많은 도시에 보낼 수 있으며, 가장 먼 거리는 얼마인지 구하는 문제이다. 

- 다익스트라 알고리즘을 활용한 문제로 heapq를 활용한다.

2. 코드

import heapq

# 입력
INF = int(1e9)
a, b, start = map(int, input().split())
graph = [[] for _ in range(a+1)]
distance = [INF]*(a+1)

for _ in range(b):
    x, y, z = map(int, input().split())
    graph[x].append((y, z)) # 노드, 거리

# 다익스트라 알고리즘
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 graph2 in graph[now]:
            cost = dist + graph2[1]
            if cost < distance[graph2[0]]:
                distance[graph2[0]] = cost
                heapq.heappush(q, (cost, graph2[0]))

# 실행 및 출력
dijkstra(c)
max_distance = 0
count = 0
for i in distance:
    if i != INF and i != 0:
        count+=1
        max_distance = max(max_distance, i)
count, max_distance


"""
3 2 1 (node, edge, start)
1 2 4
1 3 2
>> (2, 4) (count, max_distance)
"""

3. 코멘트

- 다익스트라 알고리즘의 경우 암기를 해야할 필요가 있을 것 같다.

- 이론을 문제에 접목시키면 바로 답이 되는 경우가 있는 것 같다.