[백준] 1753번 : 최단경로 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1753번: 최단경로

 

1. 문제 설명

2. 풀이과정

해당 문제는 시작점과 다른 노드와 관련된 최단 경로의 경로값을 구하는 문제이다.

다익스트라 알고리즘의 가장 기본적인 형태를 구현할 수 있는지 물어보는 문제라고 할 수 있다.

 

다익스트라 알고리즘의 핵심 이론

1. 인접 리스트로 그래프 구현하기
   • 인접 리스트에 연결한 데이터 자료형은 [노드, 가중치] 같은 형태로 선언하여 연결한 점도 잘 봐야 한다.
2. 최단 거리 리스트 초기화하기
   • 출발 노드는 0, 이외의 노드는 무한으로 초기화
   • 무한은 적당히 큰 값을 사용하면 됨
3. 값이 가장 작은 노드 고르기
   • 최단 거리 리스트에서 현재 값이 가장 작은 노드를 고른다.
   • 이때 늘 최단 거리 리스트에서 현재 값이 가장 작은 노드를 쉽게 고르기 위해 우선순위 큐를 사용한다.
   • 우선순위 큐에 [거리, 노드] 같은 형태로 저장하여 거리를 기준으로 최단 거리 값이 자강 작은 노드를 구한다.
4. 최단 거리 리스트 업데이트하기
   • 선택된 노드에 연결된 에지의 값을 바탕으로 다른 노드의 값을 업데이트한다.
   • 1단계에서 저장해 놓은 연결 리스트를 이용해 현재 선택된 노드의 에지들을 탐색하고 업데이트하면 된다.
   • 연결 노드의 최단 거리 = Min(선택 노드의 최단 거리 리스트의 값 + 에지 가중치, 연결 노드의 최단 거리 리스트의 값)
5. 과정 3~4를 반복해 최단 거리 리스트 완성하기
   • 선택 노드가 될 때마다 다시 선택되지 않도록 방문 리스트를 만들어 처리한다.
   • 모든 노드가 선택될 때까지 반복하면 최단 거리 리스트가 완성된다.

다익스트라 알고리즘은 출발 노드와 그 외 노드 간의 최단 거리를 구하는 알고리즘이다.

많은 사람이 다익스트라 알고리즘이 출발 노드와 도착 노드 간의 최단 거리를 구하는 알고리즘이라고 생각하는 경향이 있는데, 실제로 완성된 최단 거리 리스트는 출발 노드와 이외의 모든 노드 간의 최단 거리를 표현한다.

 

슈도코드

1. V(노드 개수), E(에지 개수) 입력받기
2. K(출발 노드) 입력받기
3. graph(에지 데이터 저장 인접 리스트) 생성
4. for 에지 개수만큼 반복:
   1. u(시작 노드), v(도착 노드), w(가중치) 입력받기
   2. 인접 리스트에 에지 정보 저장
5. distance(거리 저장 리스트) 초기화
6. visited(방문 여부 저장 리스트) 초기화
7. 거리 리스트에서 출발 노드의 값을 0으로 설정
8. pq(우선순위 큐) 생성
9. pq에 [거리, 출발 노드]를 넣고 시작
10. while(큐가 빌 때까지):
    1. now(우선순위 큐에서 최단 거리를 갖는 노드 가져오기)
    2. now_v(현재 선택된 노드에서 출발 노드를 가져옴)
    3. 만약 (현재 선택된 노드의 출발 노드를 방문한 적이 있으면): 그냥 넘어감
    4. 현재 선택된 노드의 출발 노드를 방문한 노드로 저장
    5. for 현재 선택 노드의 에지 개수:
       1. next_v(다음 노드에서의 도착 노드)
       2. weight(다음 노드에서의 도착 노드의 가중치)
       3. if (연결 노드 방문 전 and 연결 노드의 최단 거리 > 현재 선택 노드 최단 거리 + 가중치):
          1. 연결 노드 최단 거리 업데이트
          2. 우선순위 큐에 연결 노드 추가
11. for 노드의 개수:
    1. if (방문한 노드): 거리 리스트에서 해당 노드의 최단 거리 출력
    2. else: INF 출력

 

반응형

3. 소스코드

import sys
from queue import PriorityQueue

V, E = map(int, sys.stdin.readline().split())
K = int(sys.stdin.readline())

graph = list([] for _ in range(V + 1))
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([v, w])

distance = list(sys.maxsize for _ in range(V + 1))
visited = list(False for _ in range(V + 1))

distance[K] = 0

pq = PriorityQueue()
pq.put([0, K])

while (pq.qsize() > 0):
    now = pq.get()
    now_v = now[1]
    if (visited[now_v]):
        continue

    visited[now_v] = True
    for next in graph[now_v]:
        next_v = next[0]
        weight = next[1]
        if (distance[next_v] > distance[now_v] + weight):
            distance[next_v] = distance[now_v] + weight
            pq.put([distance[next_v], next_v])

for i in range(1, V + 1):
    if (visited[i]):
        print(distance[i])
    else:
        print("INF")