[최단 경로] 최단 경로 알고리즘 (5) 실전 문제 - 전보

이코테 p.262 실전 문제 - 전보

입력 예시

3 2 1 1 2 4 1 3 2

출력 예시

2 4

내 소스코드

• 다익스트라 알고리즘 사용
  • 메시지를 보내고자 하는 도시 c를 시작 노드로 설정
  • c로부터의 최단 시간 정보가 존재하는 도시를 카운트하여 메시지를 받는 도시 개수를 구함
  • c로부터의 최단 시간 정보들 중에서 최댓값을 구하여 메시지 전송에 걸리는 총 시간을 구함

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

# 도시 개수 n, 간선 개수 m, 메시지를 보내고자 하는 도시 c 입력 받기
n, m, c = map(int, input().split())

# 그래프 입력 받기
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]))

# 시작 노드를 c로 하여 다익스트라 알고리즘 수행
dijkstra(c)

# 최단 시간 정보가 존재하는, 즉 도달할 수 있는 도시 개수 카운트
# 단, 시작 노드는 외
cnt = 0
for i in range(n + 1):
  if distance[i] != INF and i != c:
    cnt += 1

# 메시지 전송에 걸리는 총 시간, 즉 최단 시간 정보 중에서 최댓값 구하기
time = 0
for i in range(n + 1):
  if distance[i] != INF and time < distance[i]:
    time = distance[i]

# 결과 출력
print(cnt, time)

교재 소스코드

• 한 도시에서 다른 도시까지의 최단 거리 문제로 치환할 수 있음
• 따라서 다익스트라 알고리즘 이용
•  N과 M의 범위가 충분히 크기 때문에 우선순위 큐를 이용한 개선된 다익스트라 알고리즘 이용

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9) # 무한을 의미하는 값으로 10억 설정

# 노드 개수, 간선 개수, 시작 노드 입력 받기
n, m, start = map(int, input().split())

# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트 만들기
graph = [[] for _ in range(n + 1)]
# 모든 간선 정보 입력받기
for _ in range(m):
  x, y, z = map(int, input().split())
  # x번 노드에서 y번 노드로 가는 비용이 z라는 의미
  graph[x].append((y, z))

# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n + 1)

# 다익스트라 알고리즘
def dijkstra(start):
  q = []
  # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여 큐에 삽입
  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 = 0
# 도달할 수 있는 노드 중에서 가장 멀리 있는 노드와의 최단 거리
max_distance = 0
for d in distance:
  # 도달할 수 있는 노드인 경우
  if d != INF:
    count += 1
    max_distance = max(max_distance, d)

# 시작 노드는 제외해야 하므로 count - 1
print(count - 1, max_distance)