[백준/1238/Python] 파티

문제

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가 들어온다.

모든 학생들은 집에서 X에 갈 수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

---

각 위치에서 파티 장소로 가는 최소 값과 파티 장소에서 각 위치로 돌아가는 최소 값이 가장 큰 경우를 구하는 문제다.

언뜻 보면 플로이드 와샬 알고리즘(각 위치에서 파티 장소로 가는 최솟값)과 다익스트라 알고리즘(파티 장소에서 각 위치로 돌아가는 최소 값)을 합치면 풀릴 것 같지만 플로이드 와샬 알고리즘의 시간 복잡도가 O(n^3)이기 때문에 (for문이 3번 돌아간다.) 시간 초과에 걸려버리게 된다.

 

이 문제는 조금만 발상을 바꾸면 쉽게 풀리는 문제였다. 발상을 못 바꿨기 때문에 엄청나게 고생한 문제......

문제에서 제시한 예시를 그래프로 바꿔보면 다음과 같다.

급하게 만든 그래프...

파티 장소인 2번 정점은 빨간색으로 표시했다. 이 상태에서 2번 정점에서 각 위치로 이동하는 최소 경로를 구하는 것은 다익스트라 알고리즘을 한 번 수행하는 것으로 깔끔하게 해결이 된다.

 

그러나 문제는 각 위치에서 파티 장소로 이동하는 경우다. 다익스트라 알고리즘은 한 정점에서 다른 여러 정점으로 이동하는 최소 경로라 다익스트라를 쓰지는 못하겠고, 그렇다고 플로이드 와샬 알고리즘을 쓰자니 시간 초과에 걸리고....

 

결론부터 말하자면, 해당 문제는 다익스트라 알고리즘을 두 번만 시행하면 깔끔하게 해결된다!!

다음 그림을 보자

 위에 그림과 차이가 무엇인지 느껴지는가? 바로 그래프의 방향이 역방향이라는 점이다. 그래프의 방향을 역방향으로 준 상태로 파티장소를 기준으로 다익스트라 알고리즘을 수행하게 되면 각 위치에서 파티 장소로 가는  최솟값을 구하는 것과 같은 값이 나오게 된다. 놀랍지 않은가? 살짝 문제를 바꿔보게 되면 굉장히 문제가  쉽게 보인다.

알고리즘 문제를 풀다 보면 왠지 어려운 문제일 거 같고, 어렵게 꼬아서 풀려고 하게 되는데 조금은 발상을 바꿔 보는 것도 나쁘지 않아 보인다. (대부분 시간 초과 때문에 발상을 바꿔보는 거지만 ㅋㅋㅋ)

 

# N = 학생 수 , M = 단방향 도로 수 , X = 파티 장소
import sys
import heapq

def dijk(village,result,X) :
    result[X-1] = 0 #파티 장소는 최단 경로가 0
    que = [] #최소 힙
    heapq.heappush(que,(result[X-1], result.index(result[X-1]))) #(최단경로,해당 인덱스)

    while que :
        vertex, index = heapq.heappop(que) # vertex = 최단 경로, index = 해당 인덱스
        if result[index] < vertex : # 현재 경로값이 큐값에서 나온 값보다 작으면 패스
            continue
        else :
            for x, y in village[index+1].items() : #x는 현재 정점과 인접한 또 다른 정점 , y는 가중치
                weight = y + vertex
                if result[x-1] >= weight :
                    result[x-1] = weight
                    heapq.heappush(que,(result[x-1], x-1)) #(경로가중치, 인덱스)

input = sys.stdin.readline
INF = sys.maxsize
N, M, X = map(int,input().split()) #학생 수, 도로 수, 파티장소 입력
village = {} # 그래프를 표현한 딕셔너리
rev_village={} # 역방향 그래프를 표현한 딕셔너리
result = [INF for _ in range(N)] #정방향 그래프 다익스트라
rev_result=[INF for _ in range(N)] #역방향 그래프 다익스트라
for i in range(1,N+1) :
    village[i]={}
    rev_village[i]={}
for _ in range(M) :
    u,v,w = map(int,input().split()) # u = 시작점 v = 끝점 w = 가중치
    village[u][v] = w
    rev_village[v][u] = w

dijk(village,result,X) # 파티장소 -> 각 마을 최소 경로 탐색
dijk(rev_village,rev_result,X) # 역방향 그래프를 이용한  각 마을 -> 파티장소 최소 경로 탐색

for i in range(len(result)) :
    result[i] += rev_result[i]
print(max(result))

정방향 그래프 village와 역방향 그래프 rev_village를 각각 딕셔너리로 구현한다음 다익스트라 알고리즘의 결괏값을 저장하는 result와 rev_result 배열도 따로 만들어 주고 이 두 배열을 더해서 가장 큰 값을 출력하면 끝이다.