[코테 스터디] 최단 경로, 플로이드

Q37. 플로이드

🐣문제

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.


백준 링크 | https://www.acmicpc.net/problem/11404

🐥풀이

요약하면, 입력값으로 들어오는 도시 및 버스의 정보에 따라 각 도시에서 다른 도시로 갈 수 있는 최소 비용 (갈 수 없으면 0) 의 모든 경우를 구하는 것이다.

다익스트라를 활용한 최단 경로 유형을 모든 경우를 구해봄으로써 기본적으로 배워볼 수 있는 문제였다.


다익스트라 (Dijkstra) ?
최단 경로를 구하는 알고리즘 중 하나이다. 거리 테이블에 특정 노드에서 다른 노드로 가는 최단 거리 정보를 저장한다.

# 거리 테이블 초기화
distance = [int(1e9)]*(n+1)

거리 테이블을 우선 무한대로 초기화 한다. 후에 heapq를 돌면서 거리 테이블을 업데이트 시켜 나간다.

import heapq

def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0

  while q:
    cost, city = heapq.heappop(q)  # 거리비용, 도착노드

    # 거리가 cost보다 작으면 pass (거리테이블 업뎃 필요X)
    if distance[city]<cost: continue
     
    for node in graph[city]:
    	# 거리 최소비용으로 업데이트
      if distance[node[0]] > cost+node[1]:
        distance[node[0]] = cost+node[1]
        heapq.heappush(q, (cost+node[1], node[0]))

위와 같이 다익스트라(dijkstra) 알고리즘을 구현한다. heapq를 활용하여 (거리, 도착노드)를 push 및 pop 하여 거리 테이블을 업데이트 해간다.

start 노드를 기준으로 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 같은 노드끼리의 거리는 0이므로 처음에는 (0, start)로 queue에 삽입한다.

이제 queue가 빌 때까지 계속 돌면서 거리 테이블을 업데이트 한다.
거리비용 및 도착노드를 pop하여 도착노드까지의 거리를 업데이트 한다. 여기서, 최소 거리로 구해야하므로 거리비용이 거리 테이블의 값보다 작은 지 판단하여 작을 경우만 테이블을 업데이트 하고 새로운 최소 거리와 함께 해당 노드를 queue에 새로 push 한다.


최소 거리가 테이블에 모두 저장되면 q에는 더 이상 push 되지 않고, 반복문도 끝나고 최단 경로를 저장하는 거리 테이블을 얻을 수 있다.


문제에서는 모든 노드 사이의 최단 거리를 구하라고 했으므로, 각 노드를 출발점으로 하여 dijkstra 한 후 거리 테이블을 출력하면 원하는 답을 얻어낼 수 있다.

🐓코드

import heapq

# 입력값
n = int(input())  # 도시의 개수
m = int(input())  # 버스의 개수

graph = [[] for _ in range(n+1)] # 버스 정보 그래프
for i in range(m):
  a, b, c = map(int, input().split())  # 시작, 끝, 비용
  graph[a].append([b, c])  # [도착지, 비용]

  
# 거리 테이블 초기화
distance = [int(1e9)]*(n+1)

# 다익스트라
def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  
  while q:
    cost, city = heapq.heappop(q)  # 거리비용, 도착도시
    
    # 거리가 cost보다 작으면 pass
    if distance[city]<cost:
      continue
      
    for node in graph[city]:
      # 거리가 cost+도착비용 보다 크면 거리 업데이트 및 큐 push
      if distance[node[0]] > cost+node[1]:
        distance[node[0]] = cost+node[1]
        heapq.heappush(q, (cost+node[1], node[0]))


# 모든 노드 사이의 최단 거리 구하기
for i in range(n):
  # 다익스트라 (출발도시 i+1)
  dijkstra(i+1)
  
  # 못 가는 부분은 0 처리
  for j in range(1,n+1):
    if distance[j]==int(1e9):
      distance[j] = 0
      
  # 최소거리 테이블 출력
  print(" ".join(map(str, distance[1:])))
  
  # 최단거리 테이블 초기화
  distance = [int(1e9)]*(n+1)

⭐2022.05.10

최단 거리와 그래프 이론 쪽이 스터디 중에서도 젤 어려웠는데 다시 다익스트라를 마주하니 새롭다 ㅎㅁㅎ.. 공부하자 ^^...