</aside>

<aside> 🔥 문제 정리

첫째줄 → v (정점의 개수), e (간선의 개수)

둘째줄 → k (시작 정점 번호)

e개의 줄 → u (시작 정점 번호), v (도착 정점 번호), w(u→v로 가는 비용)

예제

</aside>

<aside> 🔥 접근 방법

시작 노드로부터 각 정점으로 가는 거리의 최단기록이 필요한 문제이므로

기본적인 다익스트라 알고리즘으로 풀 수 있을 것 같다.

다른 방법으로는 플로이드가 있지만, 아마 시간 복잡도 때문에 제출 시 통과를 못할 것 같다.

그래도 두가지 방법으로 풀어보자.

</aside>

Heap을 이용한 다익스트라 알고리즘 풀이

<aside> 🔥 코드

전체 코드

노드 개수, 간선 개수, 시작점 입력값 받고 그래프 생성

v, e = map(int, input().split())
k = int(input())

graph = [[] for _ in range(v + 1)]

간선 개수만큼 출발 노드, 도착 노드, 비용 입력값으로 받아 그래프에 입력
```
for _ in range(e):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
```

다익스트라 함수 생성

힙을 이용한 기본적인 다익스트라 알고리즘이다.

def dijkstra(graph, start):
    N = len(graph)
    dist = [INF] * N

    q = []
    heapq.heappush(q, (0, start))
    dist[start] = 0
    while q:
        acc, cur = heapq.heappop(q)
        if dist[cur] < acc:
            continue

        for adj, d in graph[cur]:
            cost = acc + d
            if cost < dist[adj]:
                dist[adj] = cost
                heapq.heappush(q, (cost, adj))
    return dist

결과값 출력

다익스트라 함수에서 받아온 거리 테이블을 순서대로 출력한다.

여기서 도달할 수 없는 지점의 경우 1e9의 값이 들어있기 때문에 문제에서 요구하는

INF로 변환하여 출력하도록 처리했다.
```
for cost in dijkstra(graph, k)[1:]:
    if cost != INF:
        print(cost)
    else :
        print("INF")
```

</aside>

Floyd-Warshall 알고리즘 풀이

<aside> 🔥 코드

전체코드

노드 개수, 간선 개수, 시작 노드 번호를 받아오고 2차원 거리 테이블 생성

# v: 노드의 개수, e: 간선의 개수
v, e = map(int, input().split())
# k: 시작 노드 번호
start = int(input())

# 2차원 거리 테이블
dist = [[INF] * (v + 1) for _ in range(v + 1)]

자기 자신에게 가는 경로 0으로 세팅

# 자기 자신 0 으로 세팅
for i in range(1, v + 1) :
    dist[i][i] = 0

출발노드, 도착노드, 비용을 입력받아 테이블에 업데이트.

# 간선 테이블에 업데이트
for _ in range(e):
    u, v, w = map(int, input().split())
    if w < dist[u][v]:
        dist[u][v] = w

점화식으로 경유지 거리 업데이트

점화식 : $D_{ab} = min(D_{ab}, D_{ak} + D_{kb})$

# 점화식으로 경유지 거리 추가
for k in range(1, v + 1):
    for a in range(1, v + 1):
        for b in range(1, v + 1):
            dist[a][b] = min(dist[a][b], dist[a][k] + dist[k][b])

마찬가지로 무한의 입력값은 INF로 출력

# 결과 출력
# 무한대일 경우 INF로
for d in dist[start][1:] :
    if d == INF :
        print("INF")
    else :
        print(d)

위 코드를 한줄로 바꿔볼 수 있을 거 같다.

[print("INF") if d == INF else print(d) for d in dist[start][1:]]

</aside>

결과

<aside> 🔥 다익스트라 vs 플로이드-워셜

dijkstra알고리즘은 간단히 통과되었는데,

예상했던데로 플로이드-워셜 알고리즘은 메모리 초과가 뜨고 실패했다. 사실 시간 초과가 뜰 줄 알았다.

Untitled

</aside>