| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 44019 | 22362 | 14970 | 48.422% |
문제
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
답안
import sys
import heapq
import math
# initialize variables
v, e, turning_point = map(int, sys.stdin.readline().split())
# reversed graph is needed, because round trip distances are what we want to get
graph = [[] for _ in range(v+1)]
reversed_graph = [[] for _ in range(v+1)]
for _ in range(e):
start, end, weight = map(int, sys.stdin.readline().split())
graph[start].append((end, weight))
reversed_graph[end].append((start, weight))
def dijkstra(graph, turning_point):
visited = [False for _ in range(len(graph))]
pqueue = [(0, turning_point)]
heapq.heapify(pqueue)
distances = [math.inf for _ in range(len(graph))]
distances[turning_point] = 0
while pqueue:
_, current_node = heapq.heappop(pqueue)
if visited[current_node]:
continue
visited[current_node] = True
for next_node, weight in graph[current_node]:
if distances[current_node]+weight < distances[next_node]:
distances[next_node] = distances[current_node]+weight
heapq.heappush(pqueue, (distances[next_node], next_node))
return distances[1:]
# apply dijkstra's algorithm twice
# node -> turning point, turning point -> node
distances_go = dijkstra(reversed_graph, turning_point)
distances_back = dijkstra(graph, turning_point)
# print answer: the maximum round trip distance
result = 0
for i in range(v):
result = max(result, distances_go[i]+distances_back[i])
print(result)풀이
이 문제는 그래프 내에서 최단 경로를 구하는 문제인데, 조건이 있다.
그것은 어느 한 점으로부터의 편도 경로를 구하는 것이 아니라, 왕복 경로를 구해야 하는 것이다.
또한 그래프는 방향이 있는 그래프로 주어지고 있다.
다익스트라 알고리즘을 사용하면 한 정점에서부터 다른 모든 정점까지의 거리들을 구할 수 있다. 다만, 일반적으로 다익스트라 알고리즘을 사용하여 그 역을 구하는 것은 불가능하다.
즉, 다른 모든 정점으로부터 특정한 하나의 정점까지의 거리를 구하는 것이 불가능하다는 이야기이다.
이 그래프는 방향이 있는 그래프이므로, 한 정점 A로부터 서로 다른 한 정점 B까지 가는 거리와, B로부터 A까지 가는 거리가 모두 다르다. 그러므로 한 정점에러부터 다른 모든 정점까지의 거리들을 구했다고 하더라도, 그것을 이용해 그 역을 구하는 것은 불가능하다.
그래서, 나는 이 문제를 그래프를 뒤집어서 다익스트라 알고리즘을 한 번 더 돌리는 것으로 해결했다.
여기서 그래프를 뒤집는다는 것은, 간선의 방향을 모두 반대로 한다는 뜻이다. 예를 들어, a→b, b→c로 이어지는 그래프가 있다고 가정하면, 뒤집힌 그래프 reversed_graph는 c→b, b→a의 간선을 갖게 되는 것이다.
이렇게 하면, 원래 다른 모든 정점으로부터 특정한 한 정점으로 오기 위해 이용하는 간선들을, 그 특정한 한 정점으로부터 다른 모든 정점으로 가기 위한 간선들로 이용할 수 있다.
그래프를 뒤집은 뒤 그 그래프에 다익스트라 알고리즘을 적용하면, 다른 모든 정점으로부터 특정한 한 정점으로 가는 최단 거리를 구할 수 있게 되는 것이다.
이렇게 다익스트라 알고리즘을 두 번 적용한 뒤 그 거리의 합이 가장 큰 것을 출력하면 정답이 된다.
이와 별개로, 필자는 다익스트라 알고리즘을 구현하는 데에서 실수가 있어 오답 판정을 받았는데,
while pqueue:
_, current_node = heapq.heappop(pqueue)
if visited[current_node]:
continue
visited[current_node] = True
for next_node, weight in graph[current_node]:
if distances[current_node]+weight < distances[next_node]:
distances[next_node] = distances[current_node]+weight
heapq.heappush(pqueue, (distances[next_node], next_node))heapq.heappush()와 같이 priority queue에 값을 넣어주는 부분에서 실수로 distances[next_node]가 아닌 weight를 넣어주면서 오답 처리가 되었다.
예전에도 이런 똑같은 실수를 한 적이 있는 것 같은데, 다음부터 주의하도록 해야겠다.
여러분도 다익스트라 알고리즘을 두 번 적용하는 아이디어를 가지고 구현했지만 어디가 틀린지 잘 모르겠다면 다익스트라 알고리즘이 제대로 구현되었는지 확인해보면 좋을 것이다.
