[BOJ - 다익스트라] 1753번 : 최단경로 (python)

백준 알고리즘 - 다익스트라 - 1753번 - 최단경로 - 파이썬

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

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인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

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

 

 

 

이 문제는 다익스트라의 가장 기본적인 문제다. 다익스트라를 공부하면 바로 풀수있는 문제인것 같다. 

 

다익스트라의 기본

- 다익스트라는 heapq 를 이용하면 빠르다.

- 최단 거리 테이블

- 연결 정보

 

 

사고과정

 

---- 메인 ----

1) 시작 노드를 정한다 > 문제에선 입력을 통해 받는다.

2) u, v, w를 입력받는다.  (u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻)

u에서 v로 가는 일방향그래프이기 때문에 graph = [[] for _ in range(V+1) ] 노드의 개수만큼 2중리스트랄 만든 다음, graph[u].append() 를 해주고, 노드번호와 가중치를 함께 묶어서 입력한다.

 

3) 최단거리 테이블을 생성한다. (노드의 개수 V+1 만큼 :: V+1은 노드번호가 1번부터 시작되기 때문에 )

최단거리를 확인하기 위해 INF = int(1e9) 라는 변수를 생성, 최단거리일경우 업데이트 할수 있게한다. 

 

---- 다익스트라 (시작노드번호) ----

0) import heapq

 

1) heapq를 사용하기 위해 q = [ ] 리스트 생성

2) heapq.heappush(q, value  )

value 부분에 시작노드이므로 거리는 (0, 시작노드번호)를 함께 묶어서 힙큐에 넣어준다.

 

3) 최단거리테이블[시작노드] = 0 으로 초기화

 

4) q가 빌때까지 반복

-- heapq.heappop(q) : 큐에서 거리(dist), 노드번호(now)를 꺼낸다.

-- 만약에 꺼낸 거리값이 최단거리테이블( distance[꺼낸 노드번호] ) 에 기록된 정보보다 값이 크면, 최단거리 정보가 아니기 때문에 continue 로 무시한다.

 

-- 그게 아니라면 최단거리 정보이므로 다음과 같은 작업을 수행한다.

-- for i in graph[꺼낸노드번호]:

  꺼낸노드번호에서 갈수 있는 노드와 거리정보를 i를 통해 한개씩 접근

   >> i[0] : 현재 노드에서 갈 수 있는 노드 번호

   >> i[1] : 현재 노드에서 갈 수 있는 노드 번호까지의 거리

 

i[0]까지의 최소비용(cost)은 >>> 현재 노드의 최소비용(dist) + i[1]  이다.

만약에 cost값이 최단 거리 테이블의 거리정보보다 작으면, 업데이트 해주고 힙큐에 정보를 넣어준다. 

 

 

이과정을 반복하면 방문할 수 있는 노드에 대하여 최단거리테이블이 모두 갱신된다.

 

 

---- 다시 메인 ----

다익스트라 함수가 끝나면 최단 거리 테이블이 모두 갱신되어있으므로

각 i번쨰 노드까지의 거리는 최단거리테이블의 정보를 출력해주면된다.

 

만약 방문하지 못한 노드는 INF(1e9)가 그대로 남아 있을테니 확인후 "INF"를 출력한다.

for i in range(1,V+1):

  if distance[i] == INF:

    print("INF")

  else: print(distance[i])

 

 

 

최종 코드

 

import sys
import heapq

input = sys.stdin.readline
INF = int(1e9)
def dijkstra(start):
    q= []
    heapq.heappush(q,(0,start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        #현재 노드와 연결된 인접 노드 확인
        for i in graph[now]:
            cost =dist+ i[1]
            if cost < distance[i[0]] :
                distance[i[0]] = cost
                heapq.heappush(q,(cost,i[0]))


#V == 5일 때 1~5까지 노드가 있는거임.
V, E = map(int,input().split())

snode = int(input()) #시작 노드

graph = [[] for _ in range(V+1)]
distance = [INF] * (V+1) #최단 거리 테이블
#연결 정보 입력
for _ in range(E):
    u,v,w = map(int,input().split())
    graph[u].append((v,w))


dijkstra(snode)

#i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력
for i in range(1,V+1):
    if distance[i] == INF:
        print("INF")
    else:
        print(distance[i])