[백준] 1753 : 최단경로 / python

1️⃣ 문제 설명

1753번: 최단경로

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오.

단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

• 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
• 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.
• 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.
• 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다.u와 v는 서로 다르며 w는 10 이하의 자연수이다.
• 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다.
• 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

• 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다.
• 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

 

2️⃣ 풀이 전 계획과 생각

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제다.

시작점에서 모든 정점까지의 최단거리다. 그리고 가중치가 있다.

⇒ 다익스트라로 그래프를 탐색하여, 최단거리를 구하자.

왜냐하면, 다익스트라는

1. 방문하지 않은 노드 중에서 가장 짧은 노드를 선택한다.
2. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여, 더 짧은 경로를 찾으면,
3. 이 경로가 제일 짧은 경로임을 알려 주기 위해 최단 거리 테이블을 갱신하기 때문이다.

1-2번을 반복한다.

⇒ 위의 과정을 통해 가중치가 다른 상태에서도 최단거리를 구할 수 있기에 다익스트라로 문제를 해결하자.

 

• vertex, edge 입력받기 and 시작점 입력받기
• graph → 인접리스트로
• 모든 정점까지 거리를 무한대로 초기화 (정답으로 가능한 최대값보다 크게)

1. 출발 vertex 설정한다.
2. 최단거리 table 초기화한다. (최단거리 table은 각 노드에 대한 현재까지의 최단거리 정보를 가진다.)
3. 방문하지 않은 vertex 중에서 최단 거리가 가장 짧은 vertex를 선택한다.
4. 해당 vertex를 거쳐 다른 vertex로 가는 weight 계산하여, 더 짧은 경로라면, 최단거리 table을 갱신한다.
5. 위의 3-4번 반복

 

3️⃣ 풀이

import heapq
import sys
input = sys.stdin.readline

vertex_num, edge_num = map(int, input().split())
start = int(input())
graph = [[] for _ in range(vertex_num + 1)]

for _ in range(edge_num):
    u, v, weight = map(int, input().split())
    graph[u].append((v, weight))

# 모든 정점까지에 대한 거리를 무한대로 초기화 해주기.
# 문제의 정답으로 가능한 거리의 최댓값보다 큰 값임을 보장해야 한다.
distance = [20001 * 10] * (vertex_num + 1)
distance[start] = 0

# 최소 힙 생성
Q = []
heapq.heappush(Q, (0, start))

# 거리 정보들이 모두 소진될 때까지 거리 갱신을 반복한다.
while Q:
    distance_x, x = heapq.heappop(Q)

    # 꺼낸 정보가 기존 정보보다 weight가 크기에, 의미없이 정보이므로 pass
    if distance[x] < distance_x: continue

    # 연결된 모든 간선들을 통해서 다른 정점들에 대한 정보를 갱신해준다.
    for u, weight in graph[x]:
        # u 까지 갈 수 있는 더 짧은 거리를 찾았다면 이에 대한 정보를 갱신하고 PQ에 기록해준다.
        if distance[u] > distance[x] + weight:
            distance[u] = distance[x] + weight
            heapq.heappush(Q, (distance[u], u))

for i in range(1, vertex_num + 1):
    # 도달할 수 있는 경우 거리 출력
    if distance[i] != 20001 * 10:
        print(distance[i])
    # 도달할 수 없는 경우
    else:
        print('INF')

 

4️⃣ 풀이하면서 생긴 질문

🤔 다익스트라는 음수 간선이 있으면 왜 안될까?

다익스트라 알고리즘은 임의의 정점을 출발 집합에 더할 때,

그 정점까지의 최단거리는 계산이 끝났다는 확신을 가지고 더한다.

만일 이후에 더 짧은 경로가 존재한다면 다익스트라 알고리즘의 논리적 기반이 무너진다.

🤔 시간복잡도를 알아보자.

T(전체 시간)

= heap에서 원소가 add된 횟수 * heap에 임의의 (v, d)라는 자료를 삽입하는 시간
+ heap에서 원소가 추출된 횟수 * heap에서 최소 d를 갖는 자료를 추출하는 시간

⇒

(heap에 임의의 (v, d)라는 자료를 삽입하는 시간 + heap에 임의의 (v, d)라는 자료를 삽입하는 시간)
+ heap에서 원소가 add된 횟수 = 간선의 갯수 ← 모든 정점은 한번씩 가치가 있는 v로 등장

⇒

(heap에 임의의 (v, d)라는 자료를 삽입하는 시간 + heap에 임의의 (v, d)라는 자료를 삽입하는 시간) * E

⇒ Primary Queue ⇒  (logE + logE) * E = O(E log E)

⇒ O(E log V)

 

5️⃣ 알게된 개념과 소감

다익스트라 알고리즘

• 가중치 ≥ 0
• 시작점에서 모든 점까지의 최단 거리
• O(E log V)

필요한 정보

• distance[v] = 시작점에서 v번 정점까지 가능한 최단 거리
• heap (v,d) 시작점에서 v까지 d만에 갈 수 있음을 확인했다.

알고리즘

1.  a. distance 배열 초기화b. heap에 (start,0)을 추가

     b. distance[i] = 0 if i == start 무한 else

2. heap이 비웠나? → 비었으면 종료

3. heap에서 가장 작은 distance를 갖는 (v, d)를 뽑는다.

4. distance[v] < d → v까지의 최단거리보다 d가 크다면, 가치없는 정보이므로 폐기

5. v, d를 통해 새로운 정보를 D에 추가한다.distance[w] = d+c

    heap에 (w, d+c)을 추가
    d + c < distance[w]

6. 2-5번 반복