이것이 코딩 테스트다 - Chapter9 최단 경로 정리

"최단 경로"란

특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘

 

이번에는 DFS, BFS와는 별개로 최단경로에 관련하여 "다익스트라"와 "플로이드 워셜" 알고리즘에 대하여 알아보겠다.

DFS, BFS와 차별점은 "간선의 값이 존재하며, 간선값에 따라 경로가 달라진다는 점이다"

 

그렇기에 GPS에서 소프트웨어의 기본 알고리즘으로 채택되는 중요한 개념이다.

 

 

 

 

 

먼저 "다익스트라" 알고리즘부터 알아보겠다.

1. 다익스트라 알고리즘

특정한 노드에서 출발하여 각 다른 노드까지의 최단 경로를 구해주는 알고리즘

다만, 음의 간선이 없을때 정상작동이 된다.

이때, 최단 거리 테이블 개념이 사용된다.

import heapq
import sys
INF = int(1e9)
input = sys.stdin.readline

#노드의 개수, 간선의 개수
n, m = map(int, input().split())
start = int(input())

graph = [[] for i in range(n+1)]
distance = [INF] * (n+1) #최단 거리 테이블

#간선 입력
for _ in range(m) :
  a, b, c = map(int, input().split()) #a->b 간선의 비용 : c
  graph[a].append((b, c))

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] #i[0] : 노드값, i[1] : 간선비용

      #갱신값이 작은경우 갱신한다
      if cost < distance[i[0]] :
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1) :
  if distance[i] == INF :
    print("INFINITY")
  else :
    print(distance[i])

이 코드가 작동되는 원리를 간단히 설명하면

 

방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 고른다 (heapq 구조를 사용해 자동으로 가져와진다)

이 노드를 기준으로 인접한 모든 노드에 대해, 현재 노드 + 연결된 간선값을 통한 새로운 거리값과, 기존에 저장된 거리값을 비교를 통해

적은값으로 계속하여 갱신된다.

이러한 과정을 heapq가 없을때까지 반복하면 최종적으로 각 노드의 거리값의 최소값만 저장되어 있다.

 

즉, 시작점을 기준으로 각 노드까지 가는 최단경로의 값이 저장되어 있다.

 

시간복잡도 : O(E logV) E : 간선수, V : 노드수

 

아주 많이 쓰이는 구조이므로 필자는 외워놓는것을 선호한다고 적혀있었다.

 

 

 

 

 

다음으로는 "플로이드 워셜" 알고리즘을 알아보겠다.

2. 플로이드 워셜 알고리즘

모든 지점(a)에서 다른 모든 지점(b)까지의 최단 경로(a->b)를 모두 구해야 하는 경우의 알고리즘이다.

다시말해, 시작점과 종료점이 각각 모든노드인 것이 특징이다.

 

이 알고리즘을 통하면, 각 노드간의 최단거리를 구할 수 있기 때문에

특정 노드를 거쳐가야 하는 경우의 최단경로 또한 손쉽게 구할 수 있다.

이때, N✕N 크기의 2차원 리스트에 최단경로값을 저장한다.

INF = int(1e9)
#노드수, 간선수
n = int(input())
m = int(input())

#무한으로 초기화
graph = [[INF]*(n+1) for _ in range(n+1)]

#시작 = 종료 간선값을 0으로 저장
for a in range(1, n+1) :
  for b in range(1, n+1) :
    if a == b :
      graph[a][b] = 0

#a->b : 간선 c
for _ in range(m) :
  a, b, c = map(int, input().split())
  graph[a][b] = c

#현재값과 현재를 거치는 모든경우를 계산하여 최소값으로 갱신한다
for k in range(1, n+1) :
  for a in range(1, n+1) :
    for b in range(1, n+1) :
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

#N*N 전체 경우를 출력한다
for a in range(1, n+1) :
  for b in range(1, n+1) :
    if graph[a][b] == INF :
      print("INFINITY", end=" ")
    else :
      print(graph[a][b], end=" ")
  print()

이코드가 작동되는 원리를 간단히 설명하면

 

N✕N 2차원 리스트를 무한으로 초기화를 한다음 a->a인 본인경로의 경우 0으로 초기화를 한다.

for문을 3중으로 경유점, 시작점, 끝점 노드를 돌리며

시작점->끝점의 최단경로 값과 시작점->경유점->끝점의 최단경로 값을 비요하여 최소값으로 저장하는 식이다.

이렇게 되면 각 노드간의 최단거리값이 저장되어 있다.

 

시간복잡도 : O(N^3)

 

이를 통해 경유가 있는 문제는 손쉽게 플로이드 워셜을 통해 풀 수 있다.

 

 

 

 

 

 

다음으로는 두가지 알고리즘이 적용된 두가지 예시문제를 살펴보겠다.

 

전체 노드의 개수 N과 간선의 개수 M을 입력받는다. 그리고 M개의 간선을 시작점 , 끝점을 입력받아 저장한다.

(간선값은 1이며, 간선은 쌍방으로 연결된다)

마지막으로 경유노드 K와 도착노드 X를 입력받아 1노드를 시작점으로 하였을때, 최단경로 값을 출력한다.

 

이 문제는 1->K->X의 최단거리를 구하는 문제이므로 직감적으로 바로 플로이드 워셜을 사용해야 한다는 점이 생각나야 한다.

큰 문제없이 플로이드 워셜을 통해 각 최단거리 값을 저장한 다음,

1->K값 + K->X값을 출력하면 되겠다.

import sys
input = sys.stdin.readline
INF = int(1e9)

N, M = map(int, input().split())
graph = [[INF]*(N+1) for _ in range(N+1)]

for i in range(M) :
  a, b = map(int, input().split())
  graph[a][b] = 1
  graph[b][a] = 1

X, K = map(int, input().split())

for a in range(1, N+1) :
  for b in range(1, N+1) :
    if a == b :
      graph[a][b] = 0

for k in range(1, N+1) :
  for a in range(1, N+1) :
    for b in range(1, N+1) :
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

if graph[1][K] == INF or graph[K][X] == INF :
  print(-1)
else :
  result = graph[1][K] + graph[K][X]
  print(result)

 

 

 

 

 

다음문제도 살펴보겠다.

 

전체 노드의 개수 N과 간선의 개수 M과 시작노드 C를 입력받는다.

그리고 M개의 간선을 시작점, 끝점, 간선값을 입력받아 저장한다.

이때, C노드를 기준으로 연결된 경로를 통해 갈수있는 모든 노드의 개수와, 해당 노드에 도달하는 간선합의 최대값을 구하라.

 

이문제는 시작점 C를 기준으로한 모든노드까지의 최단거리를 통한 최단거리를 구하여 최단거리 테이블을 구한다.

그 후, 최단거리 테이블 중 무한이 아닌 값의 노드 개수와 그 값들중의 간선의 최대값을 구하면 되겠다.

즉, 다익스트라를 사용하여 최단 거리 테이블을 구하면 되겠다.

import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline

N, M, C = map(int, input().split())

graph = [[] for i in range(N+1)]
distance = [INF] * (N+1)

#간선 입력
for _ in range(M) :
  x, y, z = map(int, input().split())
  graph[x].append((y, z))

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] #i[0] : 노드값, i[1] : 간선비용

      #갱신값이 작은경우 갱신한다
      if cost < distance[i[0]] :
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))

dijkstra(C)

#노드의 개수, 간선의 최대값 구하여 출력
sum = 0
time = 0
for i in range(1, N+1) :
  if i == C :
    continue
  if distance[i] != INF :
    sum += 1
    if distance[i] > time :
      time = distance[i]

print(sum, time)

 

 

이처럼 DFS, BFS와는 별개로 각 노드를 잇는 최단경로에 관한

다익스트라, 플로이드 워셜 알고리즘에 대해 알아보았다.

 

다익스트라의 경우 아주 자주 출제되는 문제 유형 중 하나로 알려져 있다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/09.%20최단%20경로

CodingTestStudy/FreeDeveloper_Cote