Algorithm
[이것이 코딩테스트다] 최단경로
- -
반응형
오늘은 최단경로를 공부한 내용을 가지고 포스팅한다. 최단경로(Shortest Path) 알고리즘은 말그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘은 다양한 종류가 있고 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있는 상태이다.
ex) 1. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우
2. 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우
참고로 코딩테스트에서는 주로 최단경로를 모두 출력하는 문제보다는 최단 거리를 출력하는 문제가 많이 출제되는 경향이 있다.
1. 가장 빠른 길 찾기
- 최단 경로 알고리즘
- 특징
- 컴퓨터공학과 학부 수준에서는 다익스트라 / 플로이드 워셜 / 벨만 포드 알고리즘 이렇게 3가지가 있음
- 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용됨.
- 다익스트라 알고리즘
- 데이크스트라(네덜란드 사람 이름) 알고리즘이라고도 함
- 특정한 노드에서 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘
- 음의 간선이 없을 때 정상적으로 동작
- GPS 소프트웨어의 기본 알고리즘
- 그리디 알고리즘으로 분류
- 알고리즘 원리
- 출발 노드 설정
- 최단 거리 테이블 초기화
- 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
- 해당 노드를 거쳐 다른 노드로 가는 비용 계산해 최단 거리 테이블 갱신
- 위 과정에서 3과 4번을 번복
- 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장해 리스트를 계속 갱신한다는 특징
- 구현 방법이 2가지 있음
- 구현하기 쉽지만 느리게 동작
- 구현하기에는 조금 더 까다롭지만 빠르게 동작
- 방법1. 구현하기 쉽지만 느리게 동작
- 시간복잡도 : O(V^2) (V는 노드의 개수를 의미)
- 선형탐색 => 최단 경로 문제에서 전체 노드 개수가 5,000개 이하라면 문제 해결 가능
- 최단 경로 문제에서 전체 노드 개수가 10,000개가 넘어간다면 해결 어려움 => 개선된 다익스트라 알고리즘 이용
#import sys
#input = sys.stdin.readline
INF = int(1e9) # 무한 10억 설정
# 노드의, 개수, 간선의 개수 입력받기
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())
# a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].append((b,c))
print(graph)
# 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드의 번호를 반환
def get_smallest_node():
smallest_node_index = 0 # 가장 거리가 짧은 노드(인덱스)
min_value = INF
for i in range(n+1):
if visited[i] == False and distance[i] < min_value:
min_value = distance[i]
index = i
return index
def dijkstra(start):
# 시작 노드에 대해서 초기화
distance[start] = 0
visited[start] = True
# 시작노드를 거쳐 다른 노드로 가는 비용을 distance 갱신
for j in graph[start]:
print(f"j : {j}")
print(f"j[0] : {j[0]}")
print(f"j[1] : {j[1]}")
distance[j[0]] = j[1] #j j[0]은 도착 노드 , j[1]은 시작노드에서 도착노드로 가는 비용
print(distance)
# 시작 노드를 제외한 전체 n-1개의 노드에 대해 반복
for i 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
3
# 다익스트라 알고리즘 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한("INFINITY")이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
- 방법2. 개선된 다익스트라 알고리즘
- 시간복잡도 : O(ElogV) (V는 노드의 개수, E는 간선의 개수를 의미)
- 힙 자료구조를 사용 => 특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음.
- 선형 시간이 아닌 로그 시간이 걸림 => N = 1,000,000 일때, log2의N이 약 20! 속도가 획기적으로 빨라짐.
#import sys
#input = sys.stdin.readline
import heapq
INF = int(1e9) # 무한 10억 설정
# 노드의, 개수, 간선의 개수 입력받기
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))
print(graph)
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하고, 큐에 삽입
distance[start] = 0
heapq.heappush(q, (0, start))
while q: # 큐가 비어있지 않다면
# 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
dist, now = heapq.heappop(q)
# 현재 노드가 처리된 적이 있는 노드라면 무시
if distance[now] < dist:
continue
# 현재 노드와 연결된 다른 인접한 노드들을 확인
for i in graph[now]:
cost = dist + i[1]
# 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if cost < distance[i[0]]:
heapq.heappush(q,(cost, i[0]))
# 다익스트라 알고리즘 수행
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1, n + 1):
# 도달할 수 없는 경우, 무한("INFINITY")이라고 출력
if distance[i] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(distance[i])
- 힙 설명
- 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나
- 우선순위 큐 : 우선순위가 가장 높은 데이터를 가장 먼저 삭제
- 파이썬에서는 PriorityQueue 혹은 heapq를 사용 => heapq가 더 빠르게 동작하기 때문에 heapq사용 권장
- 첫 번째 원소를 기준으로 우선순위를 설정 => (가치, 물건)
- 내부적으로 최소 힙(Min Heap) 혹은 최대 힙(Max Heap)을 이용
- 최소 힙 : 값이 낮은 데이터가 먼저 삭제
- 최대 힙 : 값이 큰 데이터가 먼저 삭제
- 다익스트라 알고리즘의 경우는 비용이 적은 노드를 우선적으로 방문하기 때문에 최소 힙 구조를 기반으로 사용
- 플로이드 워셜 알고리즘
- 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 알고르즘
- 다익스트라 알고리즘과의 차이점
- 다익스트라 : 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택 => 해당 노드를 거쳐 가는 경로를 확인하고 최단 거리 테이블을 갱신 / 최단거리 테이블 : 1차원 리스트 / 그리디 프로그래밍으로 분류
- 플로이드 워셜 : 단계마다 거쳐가는 노드를 기준으로 수행하는 것은 동일 but, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요는 없음 / 최단거리 테이블 : 2차원 리스트 / 다이나믹 프로그래밍으로 분류
-
다익스트라 플로이드 워셜 구현방법 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택 => 해당 노드를 거쳐 가는 경로를 확인하고 최단 거리 테이블을 갱신 단계마다 거쳐가는 노드를 기준으로 수행하는 것은 동일 but, 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요는 없음 최단거리 테이블 1차원 리스트 2차원 리스트 알고리즘 분류 그리디 프로그래밍 다이나믹 프로그래밍 시간복잡도 O(V^2) or O(ElogV) O(N^3)
- 시간 복잡도 O(N^3)
- 점화식 : Dab = min(Dab, Dak + Dkb) => 'A에서 B로 가는 최소 비용'과 'A에서 K를 거쳐 B로 가는 비용'을 비교해 더 작은 값으로 갱신하겠다는 의미
INF = int(1e9)
# 노드의 개수 및 간선의 개수 입력 받기
n = int(input())
m = int(input())
# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
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라고 설정
a, b, c = map(int, input().split())
graph[a][b] = c
# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in ragne(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):
# 도달할 수 없는 경우, 무한("INFINITY")이라고 출력
if graph[a][b] == INF:
print("INFINITY")
# 도달할 수 있는 경우 거리를 출력
else:
print(graph[a][b], end=" ")
print()
2. 최단경로 알고리즘 문제
- 실전문제 미래도시
- 실전문제 전보
- Q 37 플로이드
- Q 38 정확한 순위
- Q 39 화상 탐사
- Q 40 숨바꼭질
반응형
Contents
소중한 공감 감사합니다