[이코테] 최단경로 - 전보

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메세지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메세지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내려면 도시 X -> Y로 가는 통로가 설치되어 있어야 한다. 어느 날 C라는 도시 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에서 보낸 메세지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분해 출력한다.

사고과정

• 특정 시작 도시 C로 지정한 문제 조건을 보고 다익스트라 알고리즘을 조심스레 예상했다. 그리고 문제를 더 읽어보니 도달한 도시들 개수를 세기만 하면 되므로 결국 특정 노드에서 모든 노드들까지의 거리를 구하는 다익스트라를 확신함
• 하지만 총 걸리는 시간을 구하라는 문제 요구를 보고 최대 힙을 구현하는 것이라고 오해했다. 예를 들어 1 -> 4번으로 가는 거리를 구해야 하는데, 루트가 1 -> 4 , 1 -> 2 -> 4 두 루트가 있는데, 각 거리 비용이 4, 6 이다. 그런데 나는 '총 걸리는 시간'을 걸리는 시간의 최댓값으로 오해해서 최대힙을 구현하느라 1시간 동안 삽질을 했다.. 문제를 잘 읽어보니 '총 걸리는 시간'은 결국 '최단 거리 비용'임을 눈치채고 다익스트라 알고리즘 베이스 코드로 쉽게 구현했다. 문제에서 자꾸 놓치는 점이 있어서 아쉽다. 문제를 한 번 읽더라도 천천히 모든 요구사항을 눈치 챌 수 있도록 차근차근 읽어야 할 듯 하다.

풀이

1. 나의 풀이

import heapq

n, m, c = map(int, input().split())
INF = 1001
distance = [INF] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    graph[x].append((y, z))
# 시작노드(c) 처리
q = []
distance[c] = 0
heapq.heappush(q, (0, c))
while q:
    dist, node = heapq.heappop(q)
    if dist > distance[node]:
        continue
    for next in graph[node]:
        cost = distance[node] + next[1]
        if cost < distance[next[0]]:
            distance[next[0]] = cost
            heapq.heappush(q, (cost, next[0]))

count = 0
max_dist = -1
for i in range(1, n+1):
    if distance[i] == 0 or distance[i] == INF:
        continue
    count += 1
    max_dist = max(max_dist, distance[i])

print(count, max_dist)

2. 책의 풀이

마지막 출력문 표출할 때만 나의 풀이와 다르다.

 

import heapq

n, m, c = map(int, input().split())
INF = 1001
distance = [INF] * (n+1)
graph = [[] for _ in range(n+1)]
for _ in range(m):
    x, y, z = map(int, input().split())
    graph[x].append((y, z))
# 시작노드(c) 처리
q = []
distance[c] = 0
heapq.heappush(q, (0, c))
while q:
    dist, node = heapq.heappop(q)
    if dist > distance[node]:
        continue
    for next in graph[node]:
        cost = distance[node] + next[1]
        if cost < distance[next[0]]:
            distance[next[0]] = cost
            heapq.heappush(q, (cost, next[0]))

count = 0
max_dist = 0
for d in distance:
    if d != INF:
        count += 1
        max_dist = max(max_dist, d)

print(count-1, max_dist)