[BOJ] 백준 1753 최단 경로 구하기 (python 파이썬)

백준 1753 최단 경로 구하기

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

1753번: 최단경로

 

Step 1 문제 분석하기

문제

모든 간선의 가중치가 10 이하의 자연수.

자연수는 양수이므로 모든 간선이 양수 -> 백준 1753은 전형적인 다익스트라 알고리즘 문제이다.

 

• 다익스트라 알고리즘 수행 과정

1. 거리 리스트에서 아직 방문하지 않은 노드 중 현재 값이 가장 작은 노드를 선택한다. 즉, 우선순위 큐에서 데이터를 뽑아온다.
2. 해당 노드와 연결된 노드들의 최단 거릿값을 다음 공식을 이용해 업데이트한다.

- [연결 노드 거리 리스트 값]보다 [선택 노드의 거리 리스트 값 + 에지 가중치] 가 더 작은 경우 업데이트 수행

- 업데이트가 수행되는 경우 연결 노드를 우선순위 큐에 삽입

  

   3. 큐가 빌 때까지 1~2를 반복한다.

 

 

위 그림은 백준 예제 입력을 기반으로 그렸습니다!

 

Step 2 수도코드

V(노드 개수), E(에지 개수)
K (출발 노드)
distance(거리 저장 리스트)
visited (방문 여부 저장 리스트)
myList(에지 데이터 저장 인접 리스트)
q(다익스트라를 위한 우선순위 큐)

for 에지 개수만큼 반복:
	인접 리스트에 에지 정보 저장
    
 
 # 다익스트라 수행
 출발 노드는 우선순위 큐에 넣고 시작 # 자동으로 거리가 최소인 노드를 선택
 거리 리스트에 출발 노드의 값을 0으로 설정
 
 while 큐가 빌 때까지:
	우선순위 큐에서 노드 가져오기
    현재 선택된 노드를 방문한 적이 있는지 확인
    현재 노드를 방문 노드로 업데이트 
    for 현재 선택 노드의 에지 개수:
    	if 연결 노드 방문 전 and 현재 선택 노드 최단 거리 + 비용 < 연결 노드의 최단 거리:
        	연결 노드 최단 거리 업데이트
            우선순위 큐에 연결 노드 추가
            
 완성된 거리 리스트를 탐색해 출력

 

Step 3 코드 작성

import sys
input = sys.stdin.readline
from queue import PriorityQueue

V,E = map(int, input().split())
K = int(input())

# 거리 저장 리스트 (충분히 큰 값으로 초기화)
distance = [sys.maxsize]*(V+1)

#방문 여부 저장 리스트
visited = [False] * (V+1)

myList = [ [] for _ in range(V+1)]
q = PriorityQueue()

for _ in range(E):
  u,v,w = map(int,input().split())
  myList[u].append((v,w))
    
q.put((0,K))
distance[K] = 0

while q.qsize() > 0:
  current = q.get()
  c_v = current[1]
  if visited[c_v]:
    continue
  visited[c_v] = True
    
  for tmp in myList[c_v]:
    next = tmp[0]
    value = tmp[1]
    if distance[next] > distance[c_v] + value:
      distance[next] = distance[c_v] + value
      q.put((distance[next], next))
            
for i in range(1,V+1):
  if visited[i]:
    print(distance[i])
  else:
    print("INF")

 

• 참고자료

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148457 

학습 페이지