코딩테스트 관련 내용정리 (4)

최단 경로 알고리즘

---

- 가장 짧은 경로를 찾는 알고리즘을 의미한다.

- '길찾기' 문제라고도 불림

- 각 지점은 그래프에서 '노드'로 표현되고, 지점 간 연결된 도로는 그래프에서 '간선'으로 표현된다. 

 

다익스트라 최단 경로 알고리즘

---

- 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다.

- 그리디 알고리즘으로 분류된다.

<원리>

(1) 출발 노드를 설정한다.

(2) 최단 거리 테이블을 초기화 한다.

(3) 방문하지 않은 노드 중에서 최단거리가 가장 짧은 노드를 선택한다.

(4) 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

(5) (3),(4)번을 반복한다.

- '각 노드에 대한 현재까지의 최단거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다.

- 우선순위 큐(heaq)를 사용하여 시간복잡도를 낮췄다.

import heapq
import sys
input=sys.stdin.readline

INF=int(1e9)

# 노드, 간선의 갯수
n,m=map(int,input().split())
# 시작 노드 번호를 입력받기
start=int(input())
# 그래프 생성
graph = [[] for _ in range(n+1)]
# 최단거리 테이블 초기화
distance=[INF]*(n+1)

# 그래프 채우기
for _ in range(m):
  a,b,c=map(int,input().split())
  graph[a].append((b,c))

def dijkstra(start):
  q=[]
  # 초기화
  # 시작노드의 거리는 0
  heapq.heappush(q,(0,start)) # 거리와 노드
  distance[start]=0

  while q:
    # 최소 힙이므로 최단거리 노드가 pop
    dist,now=heapq.heappop(q)
    # 이미 처리된 노드라면
    if distance[now]<dist:
      continue

    # 현재 노드와 연결된 인접한 노드 확인
    for i in graph[now]: 
      cost=dist+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])

 

 

플로이드 워셜 알고리즘

---

- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 

- 다이나믹 프로그래밍

- A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용 중 더 작은 값으로 갱신

# 무한을 의미하는 상수값 설정
INF=int(1e9) # 1e9 == 10억

# 노드의 개수 및 간선의 개수
n=int(input()) # 노드
m=int(input()) # 간선

# 2차원 리스트 생성 및 초기화
# 배열인덱스를 바로 노드번호로 사용하기 위해 n+1로 설정 
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

# 간선 데이터 입력
for _ in range(m):
  a,b,c = map(int,input().split()) # a에서 b로 가는 비용은 c
  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])


# 출력
for a in range(1,n+1):
  for b in range(1,n+1):
    if graph[a][b]==INF:
      print("INF",end=" ")
    else: 
      print(graph[a][b],end=' ')

  print() # 줄바꿈

 

 

참고문헌 및 출처 | 나동빈. 2020. 이것이 취준을 위한 코딩 테스트다 with 파이썬. 한빛미디어