백준 문제 풀이 - 파티 1238번

📜 문제 이해하기

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

💡 문제 재정의

단방향 그래프가 주어질 때 파티장으로 가는 시간과 집으로 돌아오는 시간이 가장 긴 학생을 출력하자.

✏️ 계획 수립

이 문제는 2번의 다익스트라로 해결할 수 있다. 먼저 파티장으로 가는 최단 경로의 값은 단방향 그래프를 반대로 뒤집고 파티를 하는 정점에서 다익스트라를 수행하면 된다. 그 후 기존의 단방향 그래프에서 파티 정점에서 다익스트라를 수행하면 파티장에서 집으로 돌아가는 최단 경로를 구할 수 있다. 두 거리의 합을 더해 가장 큰 거리를 출력하면 된다.

💻 계획 수행

import sys
import math

status = []
distance = []
tree = []
fringe = []


def get_min_distance_idx():
    min_distance = math.inf
    min_idx = 0
    fringe_idx_ = 0
    for f, idx in enumerate(fringe):
        if min_distance > distance[idx]:
            min_distance = distance[idx]
            min_idx = idx
            fringe_idx_ = f

    return min_idx, fringe_idx_


def dijkstra(graph, start_idx):
    global status, distance, tree, fringe
    status = ['U' for _ in range(N + 1)]
    distance = [math.inf for _ in range(N + 1)]
    tree = []
    fringe = []

    tree.append(start_idx)
    status[start_idx] = 'T'
    distance[start_idx] = 0

    for i, weight in enumerate(graph[start_idx]):
        if weight > 0:
            fringe.append(i)
            status[i] = 'F'
            distance[i] = weight

    while fringe:
        # 가장 가까운 값의 노드를 트리에 추가
        next_idx, fringe_idx = get_min_distance_idx()
        tree.append(next_idx)
        status[next_idx] = 'T'
        fringe.pop(fringe_idx)

        for i, weight in enumerate(graph[next_idx]):
            # 연결된 것들 중에서
            if weight > 0:
                # fringe에 없다면 update
                if status[i] == 'U':
                    fringe.append(i)
                    status[i] = 'F'
                    distance[i] = distance[next_idx] + weight

                # 현재 경로보다 더 짧은 경로라면 업데이트
                elif status[i] == 'F' and distance[i] > (distance[next_idx] + graph[next_idx][i]):
                    distance[i] = distance[next_idx] + graph[next_idx][i]


if __name__ == '__main__':
    N, M, X = map(int, sys.stdin.readline().split())
    graph1 = [[0 for _ in range(N + 1)] for _ in range(N + 1)] # 파티로 가는길
    graph2 = [[0 for _ in range(N + 1)] for _ in range(N + 1)] # 집에 돌아오는 길
    distance_sum = [0 for _ in range(N + 1)]

    for _ in range(M):
        node1, node2, edge_weight = map(int, sys.stdin.readline().split())
        graph1[node2][node1] = edge_weight
        graph2[node1][node2] = edge_weight

    dijkstra(graph1, X)
    for i in range(N + 1):
        distance_sum[i] += distance[i]
    dijkstra(graph2, X)
    for i in range(N + 1):
        distance_sum[i] += distance[i]
    print(max(distance_sum[1:]))

🤔 회고

두개의 그래프를 활용하여 문제를 해결할 수 있었다. 파티장으로 가기위한 최단 경로는 각 정점에서 한번씩 해보는것이 아니라 그래프를 뒤집고 파티 정점에서만 하면 되기때문에 더 빠르게 풀 수 있었다.