이코테 Chapter 09 최단 경로 - 전보

문제

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내려면 도시 X -> Y로 가는 통로가 설치되어 있어야 한다. 어느 날 C라는 도시 C에서 위급 상황이 발생해 최대한 많은 도시로 전보를 보내야 한다. 메세지는 도시 C에서 출발해 각 도시 사이에 설치된 통로를 거쳐 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 정보로 주어졌을 때, 도시 C에서 보낸 메세지를 받게 되는 도시의 개수는 총 몇 개 이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성해라.

 

입력조건

• 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다.(1<= N <= 30,000 , 1 <= M <= 200,000 , 1 <= C <= N)
• 둘째 줄부터 M+1 번째 줄에 걸쳐서 통로에 대한 정보 X, Y, Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메세지가 전달되는 시간이 Z라는 의미다.(1 <= X, Y <= N , 1 <= Z <= 1,000)

출력조건

• 첫째 줄에 도시 C에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분해 출력한다.

 

접근법

1. 일단 정점의 개수가 30,000이고 간선의 개수가 200,000이니 다익스트라 알고리즘을 힙을 활용하여 써야겠다고 생각함

2. 다익스트라 알고리즘을 적용하고 따로 도시의 개수를 세는 변수와 전달 시간을 저장하는 리스트를 만들어 출력

 

[소스 코드]

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

n, m, start = map(int, input().split())

graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)

for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
  
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(start)

count_city = 0
count_time = []

for i in range(1, n + 1):
  if distance[i] != INF:
    count_city += 1
    count_time.append(distance[i])

print(count_city - 1, max(count_time))

 

오답노트 & 알아낸 것

- 일단 책에 있는 코드와는 마지막에 최장거리를 저장하는 변수에서 한 걸음 더 배워갔다. 만약에  메모리 용량이 더 한정되있는 상황이라면 리스트에 저장하지 않고 책 처럼 활용하는것도 좋은 방법인 것 같다.