이것이 코딩테스트다 전보 (Python)

문제 링크

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만 Y 에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.

어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 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

---

Test Case

입력
3 2 1
1 2 4
1 3 2

출력
2 4

---

문제 풀이

전형적인 다익스트라 문제로 항상 기억해야할 다익스트라 문제의 조건은 다음과 같다
'한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'

한 지점에서 출발하기 때문에 1차원 리스트를 이용한다는 점, 시간복잡도가 O(ElogV)인점은 기억해야 하고, 일단 다익스트라 코드 자체를 외우고 있으면 편할 것 같다.

---

Source Code

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

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

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

for _ in range(m):
    x,y,z = map(int, input().split())
    # x 에서 y로 가는 비용 z
    graph[x].append((y,z))

def dijkstra(start):
    q = []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now_node = heapq.heappop(q)
        if dist > distance[now_node]:
            continue
        
        for i in graph[now_node]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))



dijkstra(c)

length = len(distance)
ans = 0
distance[0] = -1
for i in range(1,length):
    if distance[i] != 0:
        ans += 1
    if distance[i] == INF:
        distance[i] = -1

#print(distance)
print(ans, max(distance))