[Shortest Path] 이코테 “전보” Python 풀이

문제

• 어떤 나라에는 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

풀이

• 다익스트라 알고리즘으로 해결할 수 있으며, 핵심은 아래와 같습니다.
• 도시 C에서 보낸 메시지를 받게 되는 도시의 개수
  • C가 출발 노드일 때, 도달할 수 있는 노드의 개수
• 도시 C에서 보낸 메시지를 받을 수 있는 도시들이 모두 메시지를 받는 데까지 걸리는 시간
  • C가 출발 노드일 때, 각 노드 별 최단 경로 비용 중, 가장 큰 값

예제 코드

from dis import dis
from math import dist
import sys
import heapq

# N, M, C 입력 받기
n, m, c = map(int, sys.stdin.readline().rstrip().split())

# 그래프 초기화
graph = [[] for _ in range(n+1)]

# 최소 비용 배열 초기화
distance = [int(1e9)] * (n+1)

# 간선 초기화
for _ in range(m):
    start, end, cost = map(int, sys.stdin.readline().rstrip().split())
    graph[start].append((end, cost))

# 다익스트라 함수 생성
def dijkstra(start):

    # 시작 노드 비용 초기화
    distance[start] = 0

    # 우선 순위 큐 생성
    q = []

    # 시작 노드를 우선 순위 큐에 삽입 (비용, 도착 노드)
    heapq.heappush(q, (0, start))

    # 우선 순위 큐 탐색
    while q:

        # 우선순위큐에서 최소 비용 노드 추출
        cost, now = heapq.heappop(q)

        # 시작 노드에서 추출한 노드까지의 비용이 
        # 시작 노드에서 추출 노드까지의 현재 비용보다 클 경우는 진행하지 않음
        if (cost > distance[now]):
            continue

        # 추출 노드와 인접한 노드 확인
        # neighbor = (도착 노드, 비용)
        for neighbor in graph[now]:

            # 시작 노드와 인접한 노드 간 기존 비용 vs 추출 노드를 거쳐갈 때의 비용
            if (distance[neighbor[0]] > cost + neighbor[1]):
                # 최소 비용 배열 업데이트
                distance[neighbor[0]] = cost + neighbor[1]
                # 우선순위큐에 업데이트 내용 삽입
                heapq.heappush(q, (cost + neighbor[1], neighbor[0]))

# 다익스트라 실행
dijkstra(c)

# 도시 C에서 보낸 메세지를 받게 되는 도시의 개수
count = 0
# 도시 C에서 보낸 메시지를 받을 수 있는 도시들이 모두 메시지를 받는 데까지 걸리는 시간
max = 0
for d in distance:
    # 도달할 수 있는 노드인 경우
    if (d < int(1e9)):
        count += 1
        if (d > max):
            max = d

# 시작 노드는 제거해야 하므로 count - 1을 출력
print(count - 1 , max)

참고

• 이것이 취업을 위한 코딩 테스트다. with python