백준 1238번 - 파티

파티 문제 바로 가기

풀이 날짜: 2026-03-18

baekjoon 알고리즘 문제 풀이

풀이 코드


import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n,m,x = map(int, input().split())
graph = [[] for _ in range(n+1)]
reverse_graph = [[] for _ in range(n+1)]
start = x

for _ in range(m):
    a,b,t = map(int, input().split())
    graph[a].append((b,t))
    reverse_graph[b].append((a,t))

def dijkstra(start,graph):
    distance = [INF] * (n + 1)
    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]))
    return distance

go = dijkstra(start,graph)
back = dijkstra(start,reverse_graph)

max_time = 0
for i in range(1,n+1):
    max_time = max(max_time, go[i] + back[i])
print(max_time)

접근 방법

처음 이 문제를 접했을 때, 단순히 파티 장소인 X에서 출발하여 다른 마을까지의 최단 거리만 구하면 된다고 생각했다. 그래서 다익스트라를 한 번만 실행하는 방식으로 접근했지만, 문제를 다시 읽어보니 각 학생은 자기 마을에서 X까지 갔다가 다시 돌아오는 왕복 시간을 구해야 한다는 점을 놓치고 있었다. 즉, 단순한 한 방향 최단 거리 문제가 아니라 두 방향의 최단 거리 합을 구하는 문제였다.

핵심 아이디어

이 문제의 핵심은 각 학생 i에 대해 다음 두 값을 구하는 것이다.

i → X (파티 장소로 가는 시간)
X → i (다시 집으로 돌아오는 시간) 그리고 이 둘을 더한 값이 각 학생의 총 소요 시간이며, 그 중 최댓값을 구하면 된다. —

역방향 그래프를 사용하는 이유

모든 i에 대해 i → X를 구하기 위해 매번 다익스트라를 실행하면 시간복잡도가 커진다. 이를 해결하기 위해 그래프의 방향을 뒤집은 reverse_graph를 생성했다.

원래 그래프: a → b
뒤집은 그래프: b → a 이렇게 만들고 X에서 다익스트라를 실행하면, 원래 그래프에서의 i → X 최단거리를 한 번에 구할 수 있었다.

다익스트라 구현 시 주의점

이 문제를 풀면서 가장 헷갈렸던 부분은 distance 배열의 위치였다. 처음에는 전역으로 선언했지만, 다익스트라는 시작점이 바뀔 때마다 거리 배열이 초기화되어야 하기 때문에 반드시 함수 내부에서 새로 생성해야 했다. 그리고 힙에서 꺼낸 값이 이미 처리된 값보다 크다면 무시하는 조건이 필수로 들어가야 한다.

최종 결과 계산

두 번의 다익스트라 실행 결과를 이용해 각 학생의 왕복 시간을 계산한다.

go[i] + back[i]

내가 헷갈렸던 포인트

다익스트라 한 번만 돌리면 된다고 착각함
distance를 전역으로 두고 재사용하려고 했음
i → X를 구하는 방법을 몰랐음

Vienna sausage