본문 바로가기

Problem Solving/백준BOJ

[백준BOJ] 1753번 최단경로.py

728x90
반응형
SMALL

 

백준 저지에서 최단경로를 파이썬을 통해 풀어 보았다. 

 

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

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.

www.acmicpc.net

1753번 최단경로.py

 

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

🐗 내가 직접 작성한 내 코드 🐗. Contribute to tomy9729/Algorithm development by creating an account on GitHub.

github.com

 

1753번 최단경로

문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

설명

아주 기본적인 다익스트라 문제이다. 지난 포스팅에 설명한 다익스트라를 그대로 적용하면 된다. 

코드

#1753번 최단경로.py
import heapq
import sys
import sys
input = sys.stdin.readline

def dijkstra(start) : 
    q=[]
    root[start]=0 #자기 자신에게 가는 것은 0
    heapq.heappush(q,(0,start)) #힙에 비용, 출발 노드 저장

    while q :
        cost, now = heapq.heappop(q)  # 가장 작은 가중치를 가진 노드 선택
        if root[now] < cost : #선택한 노드의 가중치가 이미 저장된 가중치보다 크면 실행x
            continue
        for next in graph[now] : 
            next_cost = cost+next[1] #현재 노드에서 다음 노드까지 가중치 계산
            if next_cost < root[next[0]] : #가중치가 더 작으면 
                root[next[0]]=next_cost #갱신
                heapq.heappush(q,(next_cost,next[0]))#heap에 추가

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

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

root = [int(1e9)]*(V+1)

dijkstra(k)
for i in range(1,V+1) : 
    if root[i] == int(1e9) : 
        print("INF")
    else :
        print(root[i])
728x90
반응형
SMALL