[백준 1238] 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고있다.

이 N명의 학생이 X번 마을에 모여서 파티를 하려고한다. 마을 사이에는 총 M개의 단방향 도로들이 있고 이 도로들을 지나갈 때는 T만큼의 시간이 소비된다.

 

각각의 학생들이 각자의 마을에서 X번 마을로 파티하러왔다가 다시 돌아갈 때 걸리는 시간이 가장 오래걸리는 시간이 몇인지 구하라.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

 

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

---

접근

만약 2번에서 파티를 한다고하면 2번에서 다른 마을로갈 때의 최소시간을 구하고 다른 마을에서 2번 마을로 갈 때의 최소시간을 더한다. 그리고 이 중 큰 값을 출력한다.

 

이를 다익스트라 알고리즘을 적용하여 풀었다.

다익스트라 알고리즘은 하나의 정점에서 다른 정점까지 갈 때의 최소비용을 구할 수 있다. 여기서 다익스트라를 N번하여 구한다.

 

구현

- 여기서 N번만큼 다익스트라를 진행한다.

- 다익스트라를 구하는 함수에서 n번에서 출발하여 다른 마을로의 최소비용을 리스트형태로 반환한다.

- 이때 n이 파티장소인 X면 최종해를 담는 answer의 각각의 마을에 비용을 더한다.

- 그렇지않다면 n번에서 파티장소로 가는 비용을 구한 것이기 때문에 이를 answer의 n에 더한다.

for n in range(N):
    dist = dijkstra(n)

    # X에서 집으로 돌아갈 때 최소비용
    if n == X-1:
        for idx, cost in enumerate(dist):
            answer[idx] += cost
    # 집에서 X로 갈 깨 최소비용
    else:
        answer[n] += dist[X-1]

 

- 다익스트라 함수는 start에서 출발하여 다른 모든 마을까지 가는데 최소비용을 구하여 반환한다.

def dijkstra(start):
    dp = [INF] * N
    dp[start] = 0
    hq = []
    heappush(hq, [0, start]) # 비용-노드

    while hq:
        # 출발->cur_node 까지의 비용이 cur_weight
        cur_weight, cur_node = heappop(hq)

        # 현재 노드와 인접한 노드를 꺼낸다.
        for next_node, weight in graph[cur_node]:
            # 출발->cur_node + cur_node->next_node
            weight += cur_weight
            if weight < dp[next_node]:
                # 출발노드 -> next_node의 최소비용
                dp[next_node] = weight
                heappush(hq, [weight, next_node])
    return dp

---

전체 코드

import sys
from heapq import heappush, heappop
input = sys.stdin.readline
'''
다익스트라: 하나의 노드에서 다른 모든 노드까지 가는데 최소비용 구하기
'''
def dijkstra(start):
    dp = [INF] * N
    dp[start] = 0
    hq = []
    heappush(hq, [0, start]) # 비용-노드

    while hq:
        # 출발->cur_node 까지의 비용이 cur_weight
        cur_weight, cur_node = heappop(hq)

        # 현재 노드와 인접한 노드를 꺼낸다.
        for next_node, weight in graph[cur_node]:
            # 출발->cur_node + cur_node->next_node
            weight += cur_weight
            if weight < dp[next_node]:
                # 출발노드 -> next_node의 최소비용
                dp[next_node] = weight
                heappush(hq, [weight, next_node])
    return dp

INF = 987654321
N, M, X = map(int, input().split())
graph = [[] for _ in range(N)]

for _ in range(M):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, w))

answer = [0] * N
for n in range(N):
    dist = dijkstra(n)

    # X에서 집으로 돌아갈 때 최소비용
    if n == X-1:
        for idx, cost in enumerate(dist):
            answer[idx] += cost
    # 집에서 X로 갈 깨 최소비용
    else:
        answer[n] += dist[X-1]

print(*answer)
print(max(answer))