1753. 최단 경로

1753 문제 보기

Difficulty : Gold 4

Status : Solved

Time : 00:23:53

접근 방식

가중치 방향 그래프이기에 다익스트라 알고리즘을 적용해 heapq로 우선순위큐를 만들어 구현했다.

최종 코드

# 최단경로 -> 주어진 시작점에서 다른 모든 정점으로의 최단 경로 구하기
import sys
import heapq
input = sys.stdin.readline

V, E = map(int, input().rstrip().split()) # 정점 개수 V, 간선 개수 E
K = int(input()) # 시작 정점
arr = [[] for _ in range(V+1)]

for _ in range(E):
  u, v, w = map(int, input().rstrip().split())
  arr[u].append((v, w)) # u -> v로의 가중치 w

def dijkstra(arr, start, V):
  costs = [float('inf')] * (V+1)
  pq = []
  heapq.heappush(pq, (0, start)) # (초기비용, 시작노드)
  costs[start] = 0

  while pq:
    cur_cost, cur_node = heapq.heappop(pq) # 우선순위 가장 높은 노드 추출
    if costs[cur_node] < cur_cost:
      continue

    for next_node, cost in arr[cur_node]:
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]:
        costs[next_node] = next_cost
        heapq.heappush(pq, (next_cost, next_node))

  return costs

costs = dijkstra(arr, K, V)

for i in range(1, V+1):
  print(costs[i] if costs[i] != float('inf') else 'INF')

• 우선순위큐에서의 그래프 형태
  시작점: (도착점, 가중치)

for _ in range(E):
  u, v, w = map(int, input().rstrip().split())
  arr[u].append((v, w)) # u -> v로의 가중치 w

• 다익스트라 코드 템플릿(기존)

import heapq

def dijkstra(graph, start, final):
	costs = {}
    pq = []
    heapq.heappush(pq, (0, start)) # (가중치, 시작노드)
    
    while pq:
    	cur_cost, cur_node = heapq.heappop()
    	if cur_node not in costs:
            costs[cur_node] = cur_cost
        for cost, next_node in graph[cur_node]:
        	next_cost = cur_cost + cost
            heapq.heappush(pq, (next_cost, next_node))
  	
    return costs[final]

• 위 1753 문제에 맞게 변형한 다익스트라 코드

def dijkstra(arr, start, V):
  costs = [float('inf')] * (V+1) # 최단경로의 경로값 출력을 위해 inf값으로 초기화
  pq = []
  heapq.heappush(pq, (0, start)) # (초기비용, 시작노드)
  costs[start] = 0 # 시작노드의 비용 0으로 초기화

  while pq:
    cur_cost, cur_node = heapq.heappop(pq) # 우선순위 가장 높은 노드 추출
    if costs[cur_node] < cur_cost: # 최저비용이 아닌 경우 continue
      continue

    for next_node, cost in arr[cur_node]:
      next_cost = cur_cost + cost
      if next_cost < costs[next_node]: # 최저비용인 경우
        costs[next_node] = next_cost
        heapq.heappush(pq, (next_cost, next_node))

  return costs

배운점

다익스트라 템플릿 코드에서 문제에서 명시한 조건을 잘 넣어주면 되는 문제다!
실수하지말기!