[백준] 1753번 최단경로 (다익스트라 문제)

사용 언어 - Python3, PyPy3

문제 -  1753번 최단경로

다익스트라  : BFS + 우선순위 큐 활용

(그래프에서 노드의 가중치에 따라 탐색해야 한다면, BFS만으로는 한계가 있다.)

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

1753번: 최단경로

 

정답

다익스트라의 3가지 중요 포인트

1. 각각의 노드에 값(가중치)을 업데이트

2. 여러 경로가 있다면 min 최솟값을 사용

3. 방문 순서 = 시작점으로부터 거리를 봐서, 짧은 순서대로 탐색해야함 (오염 방지)

 

 

BFS로 구현한 다익스트라

-> 시간복잡도 높음. 구림 -> 우선순위 큐를 사용해야 제대로 된 시간 안에 수행된다.

# BFS
from collections import deque

v, e = map(int,input().split()) # 정점개수, 간선개수
start = int(input()) # 시작 정점 번호

links = [[] for _ in range(v+1)]
visited = [0 for _ in range(v+1)]
dist = [1e9 for _ in range(v+1)] # 1e9 = 10억 = 0이 9개있다

for i in range(e):
    u,v,w = map(int,input().split()) # 출발, 도착, 가중치
    links[u].append([v,w])

q = deque()
q.append(start)
visited[start] = 1
dist[start] = 0

def shortest_finder():
    mini = 1e9
    idx = 0
    for i in range(1,n+1):
        if dist[i] <= mini:
            idx = i
            mini = dist[i]
    return idx # 지금까지 계산한 dist 중 가장 짧은 거리

while q:
    node = q.popleft()
    for nxt, weight in links[node]:
        # 1. 각 노드의 값을 업데이트
        # 2. 여러 경로가 있다면 min 비교
        # 3. 시작점으로부터 거리를 봐서, 짧은 순서대로 탐색(오염방지)
        dist[nxt] = min(dist[node] + weight, dist[nxt])
        q.append(nxt)
        visited[nxt] = 1
        idx = shortest_finder()
        
        if idx in q:
            q.remove(idx)
            q.appendleft(idx) # 우선순위 높이기
print(dist)

 

우선순위 큐를 활용한 다익스트라

 

0. 큐 활용

import heapq

 

1. input

links[출발정점].append([도착정점, 가중치])

 

최단 경로로 가중치를 저장할 리스트 생성

dist = [1e9 for _ in range(n+1)

1e9 = 10억 = 0이 9개 있다.

가까운 거리(작은 값)부터 탐색해야하므로 기본값을 큰 값(1e9)으로 만들고 값을 줄여주며 업데이트 해준다.

 

2. start 시작 노드 먼저 방문

q = []

heapq.heappush(q,[0,start])

힙에 push(입력) 할 때, (q, [가중치,시작노드])

q = [가중치, 시작노드] 와 유사한 뜻

시작점 자신은 0을 출력하라고 했으므로 dist[start] = 0

 

3. while q:

다익스트라 포인트) 시작점으로부터 거리가 짧은 순서대로 탐색

=> heappop(q)를 해줄 때, 자동으로 힙정렬되어 거리가 짧은 노드부터 입력받는다.

_w, node = heappop(q) 힙에 들어가있는 가중치랑 노드 빼주고 해당 노드 node를 먼저 방문해준다.

links[node] = [도작정점 =  다음에 방문해야 하는 노드 nxt, 가중치 weight]

 

다익스트라 포인트) 여러 경로가 있다면 가중치 최솟값 사용 

경로 1. 현재까지의 계산된 경로 거리 dist[nxt] 

경로 2. 새로 방문한 경로 거리 dist[node] + weight

새로 내가 방문한 경로의 가중치가 더 작다면 = 경로2 < 경로1

더 적은 가중치인 경로2로 방문해줘야 한다. nxt 노드로 방문 결정

dist[nxt] = 작은 가중치 = dist[nxt]+weight로 업데이트해준다.

 

다익스트라 포인트) 각 노드에 가중치 업데이트

새 노드 nxt를 방문해주면서 가중치도 업데이트 해준다.

가중치 0 -> dist[nxt]

노드 start -> nxt

heapq.heappush(q,[dist[nxt],nxt]) 방문

 

4. output

각 정점마다의 최단경로 가중치 dist를 출력해줘야 한다.

정점의 번호는 1부터 시작하므로 1부터 ~ 정점의 개수(n)까지 출력

시작점 자신은 0을 출력하라고 했으므로 무조건 0부터 출력됨

 

경로가 존재하지 않는 경우 = dist의 기본값이었던 1e9인 경우 = INF

 

 

+ pypy로 돌려야 시간 초과가 뜨지 않는다.

-> 언어에 따라서 정답여부가 바뀌는 문제는 좋은 문제가 아니다. 코테에선 그럴 일 없음!

import heapq

N,M = map(int,input().split()) # 정점개수, 간선개수
start = int(input()) # 시작 번호

links = [[] for _ in range(N+1)] # input
dist = [1e9 for _ in range(N+1)] # 가까운 거리먼저 탐색해야함

for _ in range(M):
    A,B,C = map(int,input().split())
    links[A].append([B,C])

# BFS
# start 먼저 방문
q = []
heapq.heappush(q,[0,start]) # [현재의 가중치 0, 시작노드 start]
dist[start] = 0 # 시작점은 0 출력하라고 했음

while q:
    # 시작점으로부터 거리가 짧은 순서대로 방문 = heappop
    _w,node = heapq.heappop(q)
    
    for nxt, weight in links[node]:
        # 가중치는 작은 것으로 방문한다.
        if dist[node] + weight < dist[nxt]:
            dist[nxt] = dist[node] + weight
            heapq.heappush(q,[dist[nxt],nxt]) # 가중치 업데이트
         
for j in range(1,N+1):
    if dist[j] == 1e9:
        print("INF")
    else:
        print(dist[j])

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/1753_%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C.py

 

• 다익스트라

https://blog.naver.com/ndb796/221234424646

23. 다익스트라(Dijkstra) 알고리즘