[BOJ/Python] 1238_파티

문제 출처:https://www.acmicpc.net/problem/1238

1238번: 파티

문제

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명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10

---

풀이

 

이 문제에서 집은 노드이고, 단방향 도로는 단방향 간선이다.

따라서 최단거리(최단 소요시간)로 N개의 노드에서 X번 노드까지 갔다가 다시 N개의 노드로 돌아올 때, 그중 제일 큰 소요시간을 출력하는 문제이다. 최단 소요시간을 노드 사이의 최단 거리라고 생각하면 된다.

 

우선 N개의 노드에서 X번 노드로 가는 경우를 생각해보자.

문제 그대로 N개의 노드 각각에서 X번 노드까지 다익스트라 알고리즘을 이용하여 최단거리를 구하고, X번 노드에서 N개의 각 노드까지의 최단 거리를 구할 수 있다.

하지만, 이렇게 되면 노드의 개수가 1000개인 경우에 N개의 노드에서 X번 노드까지의 최단거리를 구하기 위해 다익스트라 알고리즘을 1000번 수행해야 한다. 우선순위 큐를 이용하여 구현한 다익스트라 알고리즘의 시간복잡도의 경우, 노드의 개수 N, 간선의 개수를 M이라고 하였을 때 O(MlogN)인데, 이를 N개의 노드 각각에 대해 수행하게 되면 O(NMlogN)의 시간복잡도가 나오며, 이는 효율적이지 못하다는 결론을 내릴 수 있다.

 

따라서 이 문제의 경우, N개의 노드 각각에서 X번 노드까지의 거리를 구하기 위해서 반대로 생각해야 한다.

간선의 방향을 바꾸어 X번 노드에서 N개의 노드 각각에 대한 최단 거리를 구하는 것이다. 이는 X번 노드를 출발노드로 하여 다익스트라 알고리즘을 한 번만 수행하면 된다.

 

다음으로 X번 노드에서 N개의 노드로 가는 경우는 기존의 간선(간선의 방향을 바꾸기 전 초기상태)을 이용하여 X번 노드를 출발노드로 하여 다익스트라 알고리즘을 수행하였을 때 N개의 노드 각각의 최단 거리를 구하면 된다.

 

문제의 예제에 대한 풀이는 다음과 같다.

우선 문제에서 주어진 노드와 간선의 정보는 이렇게 된다.

• X번 노드는 2번 노드가 된다.
• 문제에서 각각의 노드 -> X번 노드 -> 각각의 노드로 가는 최단거리 중, 제일 큰 값을 구하라고 하였다.
• 우선 X번 노드 -> 각각의 노드로 가는 경우 먼저 구하면 다음과 같다. (독립된 사건이므로 먼저 구해도 상관없다.)

• 우선 모든 노드의 거리(출발 노드로부터의 거리)를 무한대로 초기화한다.
• 출발 노드에서 출발 노드까지의 거리는 0이므로 0으로 초기화한다.

• 2번 노드와 연결되어 있는 노드들에 대해서, 현재 각 노드들의 거리와 2번 노드를 거쳐서 방문했을 때의 거리를 비교한다.
• 이 경우, 각 노드들의 현재 거리는 무한대였고, 2번 노드를 거쳤을 때의 거리는 다음과 같다.
• 1번 노드 : 0 + 1 (0은 2번 노드까지의 거리, 1은 2번 노드에서 1번 노드까지의 거리)
• 3번 노드 : 0 + 5
• 비교하였을 때, 2번 노드를 거쳤을 때의 거리가 더 짧으므로 갱신해 주고, 우선순위 큐에 넣어준다.

• 현재 우선순위 큐에 존재하는 노드들 중, 거리가 가장 짧은 노드는 1번 노드이므로 1번 노드와 연결되어 있는 노드들을 살핀다.
• 각 노드들의 현재 거리와 1번 노드를 거쳤을 때의 거리를 비교한다.
• 2번 노드 : 0 < 1 + 4 이므로 갱신하지 않는다.
• 3번 노드 : 5 > 1 + 2 이므로 갱신하고 우선순위 큐에 넣어준다.
• 4번 노드 : 무한대 > 1 + 7 이므로 갱신하고 우선순위 큐에 넣어준다.

• 현재 우선순위 큐에 존재하는 노드들 중, 거리가 가장 짧은 노드는 3번 노드이므로 3번 노드와 연결되어있는 노드들을 살펴본다.
• 1번 노드 : 1 < 3 + 2 이므로 갱신하지 않는다.
• 4번 노드 : 8 > 3 + 4 이므로 갱신하고 우선순위 큐에 넣는다.

• 마지막으로 4번 노드에 대해서 수행한다. (안 해도 상관없다.)

• 최종적으로 2번 노드에서 각 노드들까지의 거리는 이렇게 된다.

 

이제 N개의 노드에서 2번 노드까지의 거리를 구하는 과정은 다음과 같다.

우선 간선의 방향을 바꾸고 시작한다.

• 간선의 방향을 바꾼 모습이다.

• 마찬가지로 각 노드들의 거리를 무한대로 초기화하고 출발지 노드의 경우 거리를 0으로 초기화한다.

• 각 노드들의 거리와 2번 노드를 거쳤을 때의 거리를 비교한다.
• 1번 노드 : 무한대 > 0 + 4 이므로 갱신하고 우선순위 큐에 넣는다.
• 4번 노드 : 무한대 > 0 + 3 이므로 갱신하고 우선순위 큐에 넣는다.

• 현재 우선순위 큐에 존재하는 노드들 중, 거리가 가장 짧은 노드는 4번 노드이므로, 4번 노드와 연결되어 있는 노드
• 1번 노드 : 4 < 3 + 7 이므로 갱신하지 않는다.
• 3번 노드 :  무한대 > 3 + 4 이므로 갱신하고 우선순위 큐에 넣는다.

• 현재 우선순위 큐에 존재하는 노드들 중, 거리가 가장 짧은 노드는 1번 노드이므로, 1번 노드와 연결되어있는 노드
• 2번 노드 : 0 < 4 + 1 이므로 갱신하지 않는다.
• 3번 노드 : 7 > 4 + 2 이므로 갱신하고 우선순위 큐에 넣는다.

• 현재 우선순위 큐에 존재하는 노드들 중, 거리가 가장 짧은 노드는 3번 노드이므로, 3번 노드와 연결되어있는 노드
• 1번 노드 : 4 < 6 + 2 이므로 갱신하지 않는다.
• 2번 노드 : 0 < 6 + 5 이므로 갱신하지 않는다.

최종 결과는 이와 같다.

따라서 예제의 경우 다음과 같은 결과가 나온다.

 

4개의 노드에서 2번 노드까지의 거리

• 1번 노드 : 4
• 2번 노드 : 0
• 3번 노드 : 6
• 4번 노드 : 3

2번 노드에서 4개의 노드까지의 거리

• 1번 노드 : 1
• 2번 노드 : 0
• 3번 노드 : 3
• 4번 노드 : 7

최종적으로 4개의 노드에서 2번 노드를 방문하고 각 노드로 돌아갔을 때의 거리는 다음과 같다.

• 1번 노드 : 5
• 2번 노드 : 0
• 3번 노드 : 9
• 4번 노드 : 10

최종적으로 4번 노드가 10의 거리로 제일 큰 값을 가지게 된다.

 

코드는 다음과 같다.

 

import sys
import heapq
 
INF = int(1e9)
 
def dijkstra(start,distacne,graph):
    queue = []
    heapq.heappush(queue,(0,start))
    distacne[start]=0
 
    while queue:
        dist,node = heapq.heappop(queue)
 
        if distacne[node] < dist:
            continue
 
        for next in graph[node]:
            cost = dist + next[1]
            if cost < distacne[next[0]]:
                distacne[next[0]] = cost
                heapq.heappush(queue,(cost,next[0]))
 
    return distacne
 
n,m,x = map(int,sys.stdin.readline().split())
 
graph_go_x = [[] for _ in range(n+1)]
graph_go_home = [[] for _ in range(n+1)]
 
distance_x = [INF for _ in range(n+1)]
distance_home = [INF for _ in range(n+1)]
 
for _ in range(m):
    a,b,t = map(int,sys.stdin.readline().split())
    graph_go_x[b].append((a,t))
    graph_go_home[a].append((b,t))
 
distance_x = dijkstra(x,distance_x,graph_go_x)
distance_home = dijkstra(x,distance_home,graph_go_home)
 
max_distance = distance_x[1] + distance_home[1]
for i in range(2,n+1):
    if distance_x[i] + distance_home[i] > max_distance:
        max_distance = distance_x[i] + distance_home[i]
 
print(max_distance)