백준 1238 - 파티 (Python3)

코드

import heapq
n, m, x = map(int, input().split())
INF = float('inf')

graph = [[] for _ in range(n+1)]

# 단방향이므로 graph에 값을 한 번만 넣어줌
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    
# 다익스트라 구현
def dijkstra(start):
    
    q = []
    
    # 각 학생들마다 소요 시간을 체크할 것이므로
    # 학생들마다의 dist_table이 필요함
    # 함수의 반환값으로 dist_table을 사용하기 위해
    # 함수 안에서 선언해줌
    dist_table = [INF for _ in range(n+1)]
    
    heapq.heappush(q, (0, start))
    dist_table[start] = 0
    
    while q:
        w, v = heapq.heappop(q)
        
        if w > dist_table[v]:
            continue
            
        for i in graph[v]:
            cost = w + i[1]
            
            if cost < dist_table[i[0]]:
                dist_table[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
    return dist_table

# 최종 정답
result = -INF

for i in range(1, n+1):
    
    # x -> x는 의미 없으므로 반복 제외
    if i == x:
        continue
        
    # 왕복 거리를 구하므로 (i -> x) + (x -> i)인 경우를 계산하여
    # result와 비교한 후, 가장 큰 값을 result로 최종 선택
    result = max(result, (dijkstra(i)[x] + dijkstra(x)[i]))
    
print(result)    

문제 해설

다익스트라 알고리즘.

개인적으로 가장 자신있는 알고리즘 유형 중 하나이다. 처음에 정말 이해가 안 가서 죽어라 연습한 보람이 느껴지는 유형 ㅎㅎ…

여타 다익스트라 문제들과 마찬가지의 로직으로 풀 수 있다. 단, 이 문제의 경우 단방향으로 주어졌을 때의 왕복 소요 시간이 가장 큰 경우를 구하라 했으므로, 최단 거리 테이블 별 학생의 도착 시간과 도착 장소에서 학생의 집까지의 소요 시간을 따로 구하여 더해주는 방식으로 풀면 간단하게 해결할 수 있다. (양방향이 아니기 때문에 x2를 하면 안됨)

기초 알고리즘 자체를 완벽히 구현할 수 있다면, 간단하게 나오는 경우 정말 쉽게 해결할 수 있는 문제인 것 같다. 이것도 꾸준한 연습의 결과라고 생각한다. 자만하지 않고 더 많은 유형의 문제를 시도해봐야겠다.