[백준] 파티

https://www.acmicpc.net/problem/1238

1238번: 파티

1. 문제 이해

각각의 도시에서 도시 -> X, X -> 도시 거리의 합이 가장 큰 값을 구하는 것이 문제입니다.

2. 문제 접근

첫번째 접근: 다익스트라

두 도시간의 최단거리를 구해야하므로 다익스트라를 생각했습니다. 각각의 도시에서 X까지의 최단 거리를 다익스트라로 구하고 X->도시까지의 거리를 다익스트라로 구한 다음 거리의 합의 최대값을 구해주었습니다.

 

두번째 접근: 다익스트라

첫번째 접근에서는 각 도시에서 X까지의 최단 거리를 구하기 위해 도시별로 다익스트라를 수행히켜주었습니다. 하지만 그럴 필요 없이 역방향 그래프를 구축한 다음 X에서부터 다른 도시들까지의 거리를 해주면 그것이 곧 각 도시에서 X까지의 거리가 되게 됩니다. N번의 다익스트라를 2번만 돌려도 정답을 구할 수 있습니다.

3. 풀이

첫번째 풀이

import sys, heapq
from collections import defaultdict

INF = 101 * 10000

#sys.stdin = open("input.txt")

input = sys.stdin.readline

n, m, x = tuple(map(int, input().split()))

graph = defaultdict(list)

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

dist_fr_student = [INF for _ in range(n + 1)]
dist_fr_x = [INF for  _ in range(n + 1)]

def dijkstra(start, end, dist):
    dist[start] = 0
    q = [(0, start)]

    while q:
        d, cur = heapq.heappop(q)

        # 마지막에 도달하면 거리를 리턴
        if cur == end:
            return d

        if dist[cur] < d:
            continue

        for next_node, next_weight in graph[cur]:
            next_dist = d + next_weight

            if dist[next_node] > next_dist:
                dist[next_node] = next_dist
                heapq.heappush(q, (next_dist, next_node))

for i in range(1, n + 1):
    if i == x:
        dijkstra(i, -1, dist_fr_x)
    else:
        temp = [INF for _ in range(n + 1)]
        dist_fr_student[i] = dijkstra(i, x, temp)

ans = 0

for i in range(1, n + 1):
    if i == x:
        continue

    ans = max(ans, dist_fr_student[i] + dist_fr_x[i])

print(ans)

 

 

두번째 풀이

import sys, heapq
from collections import defaultdict

INF = 101 * 10000

#sys.stdin = open("input.txt")

input = sys.stdin.readline

n, m, x = tuple(map(int, input().split()))

graph = defaultdict(list)
reverse_graph = defaultdict(list)

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

dist_fr_student = [INF for _ in range(n + 1)]
dist_fr_x = [INF for  _ in range(n + 1)]

def dijkstra(start, dist, gr):
    dist[start] = 0
    q = [(0, start)]

    while q:
        d, cur = heapq.heappop(q)

        if dist[cur] < d:
            continue

        for next_node, next_weight in gr[cur]:
            next_dist = d + next_weight

            if dist[next_node] > next_dist:
                dist[next_node] = next_dist
                heapq.heappush(q, (next_dist, next_node))

dijkstra(x, dist_fr_student, reverse_graph)
dijkstra(x, dist_fr_x, graph)

ans = 0

for i in range(1, n + 1):
    if i == x:
        continue

    ans = max(ans, dist_fr_student[i] + dist_fr_x[i])

print(ans)

4. 회고

어렵지 않게 다익스트라를 활용하여 풀이할 수 있었습니다. 단방향 그래프라서 처음에는 위상 정렬을 생각해보았는데 최단 경로를 구해야하기에 다익스트라로 풀이하였습니다.

5. 배운점

각 지점에서 한점까지의 거리는 역방향 그래프를 구축해서 목적지에서 다른 모든 점까지의 다익스트라로 구해주면 된다.