[CodingTest] 전보 ( 최단거리 )

◎ 문제

• 어떤 나라에는 N개의 도시가 있다.
• 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다.
• 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다.
• 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다.
• 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.
• 어느 날 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에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.

 

- 입력 예시

3 2 1
1 2 4
1 3 2

 

- 출력 예시

2 4

 

 

◎ 문제풀이

 

시작점이 정해져 있다. 특정 노드를 경유해도 되고 안 해도 된다. 방향그래프이고 모든 비용이 양수이다. 이 조건을 만족하는 최단거리 알고리즘은 다익스트라 알고리즘이다. 

 

[Algorithm] 다익스트라 알고리즘(Dijkstra)이란?

 

다익스트라 알고리즘 개념은 위 포스팅을 참고하면 된다. 

 

[Algorithm] 개선된 다익스트라 알고리즘

 

다익스트라 알고리즘은 이동할 노드를 선택할 때 가장 비용이 적은 노드를 선택한다. 선택 알고리즘은 우선순위 큐를 이용하면 시간복잡도가 개선된다. 자세한 내용은 위 포스팅을 참고바란다. 

 

 

◎ 코드구현

 

import heapq
import sys
input = sys.stdin.readline
INF = 1e9

n,m,start = map(int,input().split())
d = [INF]*(n+1)
graph = [[] for _ in range(n+1)]

for _ in range(m) :
  a,b,cost= map(int,input().split())
  graph[a].append((b,cost))

q = []
d[start] = 0
heapq.heappush(q,(0,start))
 
count = -1 # START 노드는 제외 ( -1 )
max_cost = -1

while q :
  cost,now = heapq.heappop(q)
  if d[now] < cost : continue

  count += 1
  max_cost = max(max_cost,cost)

  for next in graph[now] :
    next_cost = next[1] + cost
    d[next[0]] = next_cost
    heapq.heappush(q,(next_cost,next[0]))


print(count,max_cost,end=" ")

 

 

 

---

 

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서