데이크스트라? 다익스트라? 디익스트라? (#1238번)

#1238 파티 https://www.acmicpc.net/problem/1238

 

처음 dfs, bfs를 고민하다가 다익스트라라는 사실을 깨달았다.

 

import heapq, sys
INF = sys.maxsize
    
n, m, x = map(int, input().split())

maps = [[] for __ in range(n+1)]

for _ in range(m):
    start, dest, weight = map(int, input().split())
    # 단방향 도로
    maps[start].append([weight, dest])

# 다익스트라 돌리기
# 전체 -> x 방향,
# x -> 전체 방향

def dijkstra(n, start):
    heap = []
    heapq.heappush(heap, [0, start])
    weights = [INF]* (n+1)
    weights[start] = 0

    while heap:
        weight, node = heapq.heappop(heap)
        if weight > weights[node]:
            continue
        for w, n in maps[node]:
            new_w = weight + w
            if weights[n] > new_w:
                weights[n] = new_w
                heapq.heappush(heap, (new_w, n))
    return weights

back = dijkstra(n, x)
goNback = [dijkstra(n, i)[x] + back[i] for i in range(1, n+1)]
print(max(goNback))

 

 

왕복 최단거리를 구하기 위해서 여러 번 돌렸다.

각 노드에서 x에 도달하는 최단거리, x에서 각 노드에 도달하는 최단거리.

 

맞추긴 했는데, 이게 최선일까?

싶어서 다른 여러 답안을 봤는데 비슷하다.

 

아, 한 가지 주의해야되는 점은, 그래프 정보를 저장하는데 메모리를 최소한으로 사용해야한다. 따라서 인접리스트 방식으로 저장한다. 인접 행렬은 확실히 크기가 크다.

 

 

다익스트라 알고리즘의 시간복잡도는 어떻게 될까?

보통은 (노드의 개수)^2 으로 보는 것 같다.

 

위의 경우에는 n^2이라고 볼 수 있다.

n의 최대개수가 1000이었기에 통과할거란 기대를 하지 않았다.

 

근데 통과해서 참 다행이었다.