(Python/🏅4)백준 알고리즘 1753번: 최단경로

문제출처: https://www.acmicpc.net/problem/1753

1753번: 최단경로

오늘 배운 또 다른 문제2 

 

bfs와 유사하지만 더욱 어려운 문제다.

 

풀이:

import sys, heapq
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

input = sys.stdin.readline
V,E = map(int,input().split()) # vortex, edge
start = int(input())-1
dist = [float('inf')] * V # 양의 무한대
dist[start] = 0

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

hq = [(0, start)]
while hq:
    cur_w, cur_node = heapq.heappop(hq)

    for to_node, to_w in graph[cur_node]:
        d = cur_w + to_w
        if d < dist[to_node]:
            dist[to_node] = d
            heapq.heappush(hq, (d, to_node))

for i in dist:
    print(i if i!=float('inf') else 'INF')

 

input = sys.stdin.readline
V,E = map(int,input().split()) # vortex, edge
start = int(input())-1
dist = [float('inf')] * V # 양의 무한대라는 뜻 이다 음수무한대는 -inf 라고 한다
dist[start] =0 # 시작점에서 시작점은 0 이기때문에.

 

 

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

# 2차원 리스트를 만들어서
# 리스트 안에 튜플형식으로 (목적지, 가중치)
# graph[0] 을 보면 [(1,2),(2,3)] 인데 0에서 1 가는데 2점 / 0에서 2 가는데 3점이라는 뜻이다
# 0부터 시작하니깐 v-1 을 해준다


hq = [(0, start)] # 시작점 0 과 가중치 0

 

while hq:
    cur_w, cur_node = heapq.heappop(hq) # heappop 하면 트리구조에서 맨위가 최솟값 > 최솟값 가져온다

for to_node, to_w in graph[cur_node]: # 다음으로 가는곳 좌표와 가중치를 하나씩 가져와서
    d = cur_w + to_w # 원래 있던곳에 가중치와 갈곳에 가중치를 더하면 총 가중치 
    if d < dist[to_node]: 만약 총 가중치가 원래있던것 (처음에는 양의 무한대)보다 작으면 나중에는 업데이트
        dist[to_node] = d # 작은걸로 업데이트
        heapq.heappush(hq, (d, to_node))# heapq 에 거리와 갈곳 푸쉬 >> 최솟값이면 맨 위로 올라감 가중치 기준으로 정렬

for i in dist:
    print(i if i!=float('inf') else 'INF')

 

많이 풀어봐야겠다