1️⃣ 서론
이 문제는 백준 파티 문제에 대한 풀이이며 파이썬(Python)으로 해결하였다.
2️⃣ 문제 설명
n명의 학생이 x번 마을에 모여서 파티를 열기로 했다. 이 마을 사이에는 총 M 개의 도로가 있고 i번째 길을 지나는데 ti 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 하는데 이 때 가장 많은 시간이 걸리는 학생의 시간을 출력하는 문제이다.
3️⃣ 풀이
한마디로 왔다 갔다하는 최단 경로를 구하는 문제이다. 최단 경로를 듣고 다익스트라 알고리즘을 생각해낼 수 있었다. 모든 경로로 갈 때 한번, 올 때 한번 다익스트라 알고리즘을 실행해서 갈 때의 최단 경로값과 올 때의 최단 경로값을 더하여 답을 도출하였다.
코드는 다음과 같다.
4️⃣ 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import sys
import heapq
input = sys.stdin.readline
INF = 1e9
n, m, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
# 경로 입력 받기
for _ in range(m):
a, b, t = map(int, input().split())
graph[a].append((b, t))
# 다익스트라 알고리즘
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
# 갈 때의 최단경로 값과 올 때의 최단경로 값을 넣어줄 배열
tmp_arr = [[0] * (n + 1) for _ in range(n + 1)]
# 다익스트라 알고리즘 실행 후 값 저장
for i in range(1, n + 1):
distance = [INF] * (n + 1)
dijkstra(i)
for j in range(1, n + 1):
tmp_arr[i][j] = distance[j]
answer = 0
# 갈 때 + 올 때의 최단경로 값 중 가장 오래걸리는 학생 구하기
for i in range(1, n + 1):
answer = max(answer, tmp_arr[i][x] + tmp_arr[x][i])
print(answer)
5️⃣ 마치며
좀 더 최적화를 할 수 있었을 것 같은데 아직 다익스트라 알고리즘을 완벽하게 이해해서 쓰지는 못하는 것 같다. 좀더 그래프 쪽 공부가 더 필요한 것 같다.
