[Baekjoon Online Judge] 백준 1238번 파티(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 1238번 파티

(Python)

(글쓴날 : 2020.06.10)

 

---

* Baekjoon Online Judge, 백준 1238번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 1238번 파티

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/1238

1238번: 파티

---

2) 풀이 과정

* 시간 복잡도 : O(E log V)

 

학생들이 각각 한 명씩 살고 있는 N개의 마을과, 마을 별로 이어진 단방향 도로, 지나는 시간이 주어지고, 특정 마을에서 파티가 열릴 때, 제일 오래 걸리는 왕복 시간을 구하는 문제입니다.

단, 학생들은 항상 최단 시간으로 오고 갑니다.

 

저의 경우, 다익스트라를 적용하였고, Python을 사용했습니다.

우선, 주어지는 입력들을 인접 리스트로 구현한 뒤, 파티가 열리는 마을에서 다익스트라를 적용하여 집으로 돌아갈 때 걸리는 시간을 구했습니다.

그 후, 각 마을에서 파티가 열리는 마을로 가는데 걸리는 시간을 구하기 위해 단방향 경로들의 방향을 거꾸로 뒤집은 인접 리스트를 구현한 뒤, 똑같이 파티가 열리는 마을에서 다익스트라를 적용하여 총 왕복 시간의 최댓값을 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
def BFS(hq, dt, adjList):
    while(hq):
        wei, vec = heapq.heappop(hq)
 
        if dt[vec] > wei:
            dt[vec] = wei
 
            for v, w in adjList[vec]:
                heapq.heappush(hq, (w+wei, v))
 
 
N, M, X = map(int, input().split())
adjList = [[] for _ in range(N+1)]
reverseAdjList = [[] for _ in range(N+1)]
 
INF = 2147483647
bdt = [INF] * (N+1)
bdt[X] = 0
sdt = [INF] * (N+1)
sdt[X] = 0
hq = []
 
for _ in range(M):
    a, b, w = map(int, input().split())
 
    adjList[a].append((b, w))
    reverseAdjList[b].append((a,w))
 
for v, w in adjList[X]:
    heapq.heappush(hq, (w, v))
 
BFS(hq, bdt, adjList)
 
hq = []
for v, w in reverseAdjList[X]:
    heapq.heappush(hq, (w, v))
 
BFS(hq, sdt, reverseAdjList)
 
maxTime = 0
 
for i in range(1, N+1):
    if i == X:
        continue
 
    if maxTime < sdt[i] + bdt[i]:
        maxTime = sdt[i] + bdt[i]
 
print(maxTime)

---