이것이 코딩 테스트다 PART2 with python : 최단 경로
최단경로 : 특정 지점까지 가장 빠르게 도달하는 방법을 찾는 알고리즘
1. 다익스트라(Dijkstra) 최단경로 알고리즘
그래프에서 여럴개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단경로를 구해주는 알고리즘이다.
기본적으로 그리디 알고리즘으로 분류된다.
매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복한다.
1. 출발노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. **해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.**
5. 위의 과정에서 3,4를 반복한다.최단 경로를 구하는 과정에서 '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신한다는 특징이 있다. 매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하여 최단 거리를 찾는다.
2. 힙(heap)
힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중하나다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 특징이 있다.
스택 : 가장 나중에 삽입된 데이터 추출
큐 : 가장 먼저 삽입된 데이터 추출
우선순위큐 : 가장 우선순위가 높은 데이터 추출
PriorityQueue 혹은 heapq를 사용 할 수 있는데, 일반적으로 heapq가 더 빠르게 동작하기 때문에 수행 시간이 제한된 상황에서는 heapq를 사용하는 것을 권장한다.
우선큐를 사용할때 (가치,물건)으로 묶어서 우선순위 큐 자료구조에 넣을 수 있다. 또한 우선순위 큐를 구현할때는 내부적으로 최소 힙 혹은 최대 힙을 이용한다.
최소힙을 이용하는 경우, 값이 낮은 데이터가 먼저 삭제
최대힙을 이용하는 경우, 값이 큰 데이터가 먼저 삭제
기본적으로 최소힙 구조를 이용하는데 다익스트라 최단 경로 알고리즘에서는 비용이 적은 노드를 우선하여 방문하므로 최소힙 기반으로 하는 파이썬의 우선순위 큐 라이브러리를 그대로 사용하면 적합하다.
최단 거리가 가장 짧은 노드를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체한다.
방법1. 간단한 다익스트라 알고리즘
시간복잡도: O(V^2) ,v : 노드 개수
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드의 개수, 간선의 개수
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))
# 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
def get_small_node():
min_val = INF
index = 0 # 가장 최단 거리가 짧은 노드(인덱스)
for i in range(1,n+1):
if distance[i] < min_value and not visited[i]:
min_val = 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]
# 시작 노드를 제외한 전체 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 < distane[j[0]]:
distance[j[0]] = cost
dijkstra(start)
# 모든 노드로 가기 위한 최단 거리를 출력
for i in range(1,n+1):
# 도달할 수 없는 경우, 무한이라고 출력
if distance[i] == INF:
print("INFINITY")
else:
print(distance[i])방법2. 개선된 다익스트라 알고리즘 (heap)
최악경우 시간복잡도: O(ElogV)
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드의 개수, 간선의 개수
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))
def dijkstra(start):
q = []
# 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
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]
# 현재 노드를 걸쳐서,다른 노드로 이동하는 거리가 더 짧은 경우
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])3.플로이드 워셜 알고리즘
모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우에 사용할 수 있는 알고리즘이다.
시간복잡도 : O(N^3)
2차원 리스트에 최단거리 정보를 저장한다는 특징이 있다. 모든 노드에 대하여 다른 모든 노드로 가는 최단 거리 정보를 담아야하기 때문이다.
다익스트라 알고리즘 : 그리디 알고리즘
플로이드 워셜 알고리즘 : 다이나믹 프로그래밍
플로이드 워셜 알고리즘이 다이나믹 프로그래밍인 이유는 노드의 개수가 N이라고 할 때, N번만큼 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기때문이다.
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 i 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 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("INFINITY",end=" ")
else:
print(graph[a][b],end=" ")
print()실전문제 : 미래도시(난이도 2)
연결된 2개의 회사는 양방향으로 이동할 수 있다. 특정회사와 다른 회사가 도로로 연결되어 있다면 정확히 1만큼의 시간으로 이동할 수 있다.
방문판매원 A는 1번에서 출발하여 K번 회사를 방문 한 뒤에 X번 회사로 가는 것이 목표다.
이때, 방문 판매원A는 가능한 한 빠르게 이동하고자 한다.방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오.
"전형적인 플로이드 워셜 알고리즘 문제"
INF = int(1e9)
# 노드의 개수 및 간선의 개수를 입력받기
n, m = map(int, input().split())
# 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가 서로에게 가는 비용은 1이라고 설정(양방향)
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
# 거쳐 갈 노드 X와 최종 목적지 노드 K를 입력받기
x, k = map(int, input().split())
# 점화식에 따라 프로이드워셜알고리즘 수행
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])
# 수행된 결과를 출력
distance = graph[1][k] + graph[k][x]
if distance >= INF:
print("-1")
else:
print(distance)실전문제 : 전보(난이도 3)
어떤 나라에는 N개의 도시가 있다. 메세지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메세지를 받게 되는 도시의 개수는 총 몇 개 이며 도시들이 모두 메세지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.
"한 도시에서 다른 도시까지의 최단 거리 문제 : 다익스트라 알고리즘"
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
# 노드 개수, 간선 개수, 시작노드
n, m, start = map(int, input().split())
# 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트
graph = [[] for in range(n+1)]
# 최단 거리 테이블을 모두 무한으로 초기화
distance = [INF] * (n+1)
# 모든 간선 정보 입력받기
for _ in range(m):
x,y,z = map(int, input().split())
# x번 노드에서 y번 노드로 가는 비용이 z
graph[x].append((y,z))
def dijkstra(start):
q = []
# 시작노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
# (거리, 도착지)
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]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0])
dijkstra(start)
count = 0
max_distance =0
for d in distance:
if d != INF:
count +=1
max_distance = max(max_distance,d)
# 시작노드는 제외해야하므로 -1
print(count-1,max_distance)
