[이코테] 최단 경로 알고리즘 - 전보

실전 문제

import heapq
import sys

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

#노드의 개수, 간선의 개수 , 출발 지점 입력받기.
node,line,start = map(int,input().split())
#각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기
graph = [[] for i in range(node+1)]
#최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (node+1)

#모든 간선 정보를 입력받기
for _ in range(line):
  x,y,z = map(int,input().split())
  #x번 노드에서 y번 노드로 가는 비용이 z라는 뜻
  graph[x].append((y,z))

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)

 

결과

---

느낀 점

이 문제는 한 도시에서 다른 도시까지의 최단 거리 문제로 치환할 수 있으므로 다익스트라 알고리즘을 이용해서 풀 수 있다. 또한 N과 M의 범위가 3만과 20만으로 충분히 크기 때문에 우선순위 큐를 이용하여 다익스트라 알고리즘을 작성해야 한다. 결과적으로 다익스트라 알고리즘의 소스코드에서 마지막 부분만 조금 수정하여 코드를 만들 수 있었다.