[코딩테스트] 최단 경로 알고리즘

최단 경로 알고리즘

가장 짧은 경로를 찾는 알고리즘

한 지점에서 다른 지점까지의 최단 경로

한 지점에서 다른 모든 지점까지의 최단 경로

모든 지점에서 다른 모든 지점까지의 최단 경로

 

각 지점은 노드

각 지점의 연결은 간선으로 표현

 

 

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

한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산

음의 계산이 없을 때 동작

매 상황에서 가장 비용이 적은 노드를 선택하고 처리하는 과정 반복

-> 그리디 알고리즘으로 분류됨

-> 다익스트라 알고리즘은 한 단계마다 하나의 노드에 대한 최단 거리를 확실히 찾음

 

- 로직

출발 노드 설정

최단 거리 테이블 초기화 (시작점 0)

방문하지 않은 노드 중 가장 짧은 노드 선택

선택된 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신

리스트에서 방문한 기록이 없으며, 최단 거리인 노드를 선택

 

 

간단한 다익스트라 알고리즘

import sys
input = sys.stdin.readline

INF = 987654321 # 무한을 의미

n, m = map(int, input().split()) # 노드의 개수, 간선의 개수
start = int(input()) # 시작 노드 번호
graph = [[] for i in range(n + 1)] # 노드 정보를 담는 리스트
visited = [False] * (n + 1) # 방문 여부 담는 리스트
distance = [INF] * (n + 1) # 거리 정보 담는 리스트

# 사용자 간선 정보 입력
for _ in range(m):
    a, b, c = map(int, input().split()) # 출발 노드, 도착 노드, 거리
    graph[a].append((b, c))

# 미 방문 노드 중, 가장 최단 거리가 짧은 노드 번호 반환
def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]: # 가장 거리가 짧고 방문 기록이 없으면
            min_value = distance[i]
            index = i
    return index

# 다익스트라 알고리즘
def dijkstra(start):
    distance[start] = 0 # 첫 시작 노드 초기화
    visited[start] = True

    for j in graph[start]: # 시작 노드와 연결된 노드들
        distance[j[0]] = j[1] # 최소 거리 갱신

    for _ in range(n - 1): # 시작 노드를 제외한 반복
        now = get_smallest_node() # 최단 거리 노드 찾기
        visited[now] = True

        for j in graph[now]:
            cost = distance[now] + j[1] # 현재 노드 거리 + 다른 노드 거리
            if cost < distance[j[0]]: # 현재 노드를 거치는 것이 기존보다 더 빠르다면
                distance[j[0]] = cost # 값 갱신

# 실행
dijkstra(start)

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

 

 

우선순위 큐

우선순위가 가장 높은 데이터를 먼저 추출하는 자료 구조

<-> 큐 : 가장 먼저 삽입된 데이터가 먼저 추출

 

우선순위 큐는 튜플 형태로 값을 입력 시 가장 앞에 있는 원소를 기준으로 정렬함

ex) (거리, 노드), (거리, 노드) 일 때 거리 순으로 정렬

 

우선순위 큐 구현 시 최소 힙 또는 최대 힙을 사용함

최소 힙 : 값이 낮은 데이터가 먼저 추출

최대 힙 : 값이 큰 데이터가 먼저 추출

-> 파이썬 라이브러리가 제공하는 우선순위 큐는 최소 힙으로 구현되어 있음 

-> 다익스트라 알고리즘은 비용이 적은 노드를 우선적으로 처리해야 하기 때문에 최소 힙이 알맞음

import heapq

heapq.heappush(h, v) # 삽입
heapq.heappop(h) # 우선순위대로 꺼내기

# =================
# 최대 힙을 사용하고 싶다면
# 부호를 반대로 삽입하여 저장 후, 꺼낼 때 부호를 되돌리는 방식으로 사용
heapq.heappush(-h, v) # 삽입
heapq.heappop(-h) # 우선순위대로 꺼내기

 

 

우선순위 큐를 이용한 다익스트라 알고리즘

기본적으로 다익스트라 알고리즘이 동작하는 원리는 동일

현재 가장 가까운 노드를 저장하기 위한 목적을 가진 우선순위 큐를 추가적으로 이용

우선순위 큐는 거리가 갱신된 경우 해당 정보를 저장하고 있는 목적

방문처리 여부는 따로 확인하지 않음 -> 꺼낸 값과 기존 거리 값의 비교를 통해서 방문 여부 확인

 

- 로직

출발 노드 정보를 우선순위 큐에 넣음

우선순위 큐에서 원소를 꺼냄

해당 노드를 처리한적 있다면 무시, 없다면 처리

거리가 갱신된 노드 정보는 우선순위 큐에 삽입 (입력 순서 무관)

import heapq
import sys
input = sys.stdin.readline
INF = 987654321

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 = [] # 우선순위 큐

    # 시작점 정보
    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[i] # 현재 노드를 거쳐서 지나가는 거리 계산
            if cost < distance[i[0]]: # 현재 노드를 거치는 것이 기존보다 짧으면
                distance[i[0]] = cost # 갱신
                heapq.heappush(q, (cost, i[0])) # q에 신규 삽입

dijkstra(start)

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

 

 

플로이드 워셜 알고리즘

모든 노드에서 다른 모든 노드까지의 최단 경로를 계산하는 알고리즘

단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행

2차원 테이블에 최단 거리 정보 저장

-> 행은 출발 노드, 열은 도착 노드

다이나믹 프로그래밍 유형에 속함

 

점화식 : min( a->b까지 거리, (a->k까지 거리 + k->b까지 거리) )

 

-> 양방향 간선인 문제의 경우

graph[a][b] = c; graph[b][a] = c

를 모두 작성해주어야 함!

 

 

- 로직

최단 거리 테이블 초기화 (인접 노드간의 연결을 테이블에 작성)

k노드를 거쳐 가는 것(a->k + k->b)이 a->b보다 효율적인지를 비교하여 테이블 갱신

== Dab = min(Dab, Dak + Dkb)

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

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

graph = [[INF] * (n + 1) for _ in range(n+1)] # 2차원 리스트

# 자기 자신의 거리는 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()) # 시작점, 도착점, 거리
    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")
        else:
            print(graph[a][b], end=" ")
    print()

 

 

 

 

 

 

 

※ 해당 포스트는 이것이 "코딩 테스트다 with 파이썬(나동빈 저)"를 통해 학습한 내용을 정리한 것입니다.