728x90
최단 경로(Shortest Path)
- 가장 짧은 경로를 찾는 알고리즘
- 한 지점에서 다른 특정 지점까지의 최단 경로 구하기
- 모든 지점에서 다른 모든 지점까지 최단 경로 구하기
- 간선 간의 가중치가 있을 경우 활용
- 그리디, DP의 한 유형
다익스트라(Dijkstra)
- 특정 한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산
- ⭐️ 음의 간선이 없는 경우 사용
- 현실 세계의 프로그래밍을 할 때 많이 사용
- 매 상황 가장 비용이 적은 노드를 선택하므로 그리디 알고리즘으로 분류하기도 한다.
- 한번 방문한 노드일 경우 이후에 해당 노드에 대해 최단 경로가 다시 갱신되는 일은 없다.
1. 출발 노드 설정
2. 최단 거리 테이블 초기화(기본 무한)
3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
5. 3번과 4번 과정 반복- 3번과 4번 과정을 반복하는 것을 보고 그리디 알고리즘으로 분류하기도 한다.
- 다익스트라 알고리즘 수행시에 맨 마지막 노드에서는 알고리즘을 수행하지 않아도 된다.
- 이전 단계까지 수행했을 때 이미 모든 최단 경로를 도출했기 때문
다익스트라 구현 1
- 간단한 구현 방법
- 매 단계마다 1차원 테이블의 모든 원소를 순차 탐색
import sys
input = sys.stdin.readline
INF = int(1e9) # 파이썬에서는 변수에 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) # 최단 거리 테이블
'''
a: start node
b: end node
c: distance weight
'''
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): # 시작 노드 제외 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
for i in range(1, n + 1):
print(distance[i])
성능분석
- 시간 복잡도 : ${O(V^2)}$
- V : 노드 개수
- 전체 노드의 개수가 5,000 이하일때만 해당 알고리즘 사용가능
다익스트라 구현2
- 개선된 구현 방법
- 다익스트라 알고리즘의 기본 동작 원리는 동일하다.
- 가장 가까운 노드를 저장해놓는 자료구조가 리스트에서 힙으로 바뀐 것 뿐!
- 리스트 구현 방식 : ${O(N)}$
- 힙 구현 방식 : ${O(lg(N))}$
import heapq
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)]
distance = [INF] * (n + 1) # 최단 거리 테이블
for _ in range(m):
a, b, c = map(int, input().split())
graph[a].append((b, c))
def dijkstra(start):
q = []
# heap input data : (최단거리, 노드 번호)
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
# dist : 현재 노드의 최단 거리, now : 현재 노드 번호
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])) # 값이 갱신될 경우, heap에도 값 갱신
dijkstra(start)
for i in range(1, n + 1):
print(distance[i])- 위의 '다익스트라 구현 1' 코드와 비교했을 때,
get_smallest_node()와visited[]리스트가 사용되지 않는다.
성능분석
- 시간 복잡도 : ${O(ElgN)}$
- while 문은 노드 개수 (V) 이상으로 처리 되지 않는다.
- 현재 우선순위 큐에서 꺼낸 노드와 연결된 다른 노드들을 확인하는 총 횟수는 최대 간선의 개수(E)만큼 연산이 수행된다.
- E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 유사
플로이드-워셜(Floyd-Warshall)
- 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산
- 단계별로 거쳐가는 노드를 기준으로 알고리즘 수행
- 다익스트라와 달리 2차원 테이블에 최단 거리 정보 저장
- DP 알고리즘으로 분류
- 점화식
$${D_{ab} = min(D_{ab}, D_{ak} + D_{kb})}$$
a -> b보다a -> k -> b가 더 짧은 지 검사
1. 출발 노드 설정
2. 최단 거리 테이블 초기화
(입력으로 들어온 모든 거리 가중치를 테이블에 저장한다.)
3. 기존 테이블 값과 새로운 노드를 거쳐서 가는 경우를 비교하고 둘 중 더 작은 값이 들어갈 수 있도록 테이블을 갱신한다.
- 최단 거리 테이블 : 행은 출발 노드, 열은 도착 노드를 의미
플로이드-워셜 구현
import sys
input = sys.stdin.readline
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
# 그래프 가중치 값을 2차원 배열에 저장
for _ in range(m):
a, b, c = map(int, input().split())
graph[a][b] = c
'''
k: middle node
a: start node
b: end node
'''
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):
print(graph[a][b], end = ' ')
print()
성능분석
- 시간 복잡도 : ${O(N^3)}$
- 각 단계마다 ${O(N^2)}$ 연산을 노드의 개수 N번만큼 실행
- N이 500 이하일 경우 효과적으로 수행된다.
Q1. 미래도시
문제 설명
방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다.공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.
공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일하다.또한 연결된 2개의 회사는 양방향으로 이동할 수 있다.공중 미래 도시에서의 도로는 마하의 속도로 사람을 이동시켜주기 때문에 특정 회사와 다른 회사가 도로로 연결되어 있다면,정확히 1만큼의 시간으로 이동할 수 있다.
또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅의 상대는 K번 회사에 존재한다.방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 방문 판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표다. 이때 방문 판매원 A는 가능한 한 빠르게 이동하고자 한다. 방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오. 이때 소개팅의 상대방과 커피를 마시는 시간 등은 고려하지 않는다고 가정한다. 예를 들어 N = 5, X = 4, K = 5이고 회사 간 도로가 7개면서 각 도로가 다음과 같이 연결되어 있을 때를 가정할 수 있다.
(1번, 2번), (1번, 3번), (1번, 4번), (2번, 4번), (3번, 4번), (3번, 5번), (4번, 5번)이때 방문 판매원 A가 최종적으로 4번 회사에 가는 경로를 (1번 - 3번 - 5번 - 4번)으로 설정하면, 소개팅에도 참석할 수 있으면서 총 3만큼의 시간으로 이동할 수 있다. 따라서 이 경우 최소 이동 시간은 3이다.
입력 조건
- 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다. (1 ≤ N, M ≤ 100)
- 둘째 줄부터 M+1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어진다.
- M + 2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어진다. (1 ≤ K ≤ 100)
출력 조건
- 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력한다.
- 만약 X번 회사에 도달할 수 없다면 -1을 출력한다.
풀이
import sys
# n: 노드 수, m: 간선 수, x: 목표 노드, k: 중간 노드
input = sys.stdin.readline
INF = int(1e9)
n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신으로 가는 비용은 0으로 초기화
for i in range(1, n + 1):
for j in range(1, n + 1):
if i == j: graph[i][j], graph[j][i] = 0, 0
# a -> b, b -> a 비용 0으로 설정
for _ in range(m):
a, b = map(int, input().split())
graph[a][b] = 1
graph[b][a] = 1
# 플로이드 워셜
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])
x, k = map(int, input().split())
if graph[1][k] == INF or graph[k][x] == INF:
print(-1)
else:
print(graph[1][k] + graph[k][x])
- 문제에서 n의 범위가 100 이하 이므로 플로이드 워셜 알고리즘을 이용해 빠르게 풀 수 있다.
- 각 간선간의 가중치 값이 없으므로 단순히 a노드에서 b노드로 가는 비용을 1로 설정한다.
Q2. 전보
문제 설명
어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하지만 X라는 도시에서 Y라는 도시로 전보를 보내고자 한다면, 도시 X에서 Y로 향하는 통로가 설치되어 있어야 한다. 예를 들어 X에서 Y로 향하는 통로는 있지만, Y에서 X로 향하는 통로가 없다면 Y는 X로 메시지를 보낼 수 없다. 또한 통로를 거쳐 메시지를 보낼 때는 일정 시간이 소요된다.
어느 날 C라는 도시에서 위급 상황이 발생했다. 그래서 최대한 많은 도시로 메시지를 보내고자 한다. 메시지는 도시 C에서 출발하여 각 도시 사이에 설치된 통로를 거쳐, 최대한 많이 퍼져나갈 것이다. 각 도시의 번호와 통로가 설치되어 있는 정보가 주어졌을 때, 도시 C에서 보낸 메시지를 받게 되는 도시의 개수는 총 몇 개이며 도시들이 모두 메시지를 받는 데까지 걸리는 시간은 얼마인지 계산하는 프로그램을 작성하시오.
입력 조건
- 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메시지를 보내고자 하는 도시 C가 주어진다. (1 ≤ N ≤ 30,000, 1 ≤ M ≤ 200,000, 1 ≤ C ≤ N)
- 둘째 줄부터 M+1번째 줄에 걸쳐서 통로에 대한 정보 X, Y, Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며, 메시지가 전달되는 시간이 Z라는 의미다. (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 1,000)
출력 조건
- 첫째 줄에 도시 C에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력한다.
풀이
import sys
import heapq
# n: 노드 수, m: 간선 수, c: 출발 노드
input = sys.stdin.readline
INF = int(1e9)
n, m, c = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
cnt, time = 0, 0
# x: 출발 노드, y: 도착 노드, z: 가중치
for _ in range(m):
x, y, z = map(int, input().split())
graph[x].append((y, z))
def dijkstra(s):
q = []
heapq.heappush(q, (0, s))
distance[s] = 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(c)
for i in distance:
if i != INF:
cnt += 1
time = max(time, i)
print(cnt - 1, time)- 마지막에 시작노드는 제외한 도시의 개수와 최대 시간을 출력한다.
해당 포스팅의 내용은
저)나동빈님의 『이것이 취업을 위한 코딩 테스트다 with 파이썬』을
통해 공부한 내용을 토대로 작성하였습니다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 | 나동빈
출판 | 한빛미디어
발매 | 2020.08.05.
728x90
'📊 Algorithm > Paradigm' 카테고리의 다른 글
| [Python/수학] 최대공약수(GCD), 최소공배수(LCM) (0) | 2022.06.23 |
|---|---|
| [Python/수학-정수론] 에라토스테네스의 체 (0) | 2022.06.02 |
| [알고리즘 대비 - 이코테] 7. 다이나믹 프로그래밍 (0) | 2022.03.30 |
| [알고리즘 대비 - 이코테] 6. 이진 탐색 (0) | 2022.02.10 |
| [알고리즘 대비 - 이코테] 5. 정렬 (0) | 2022.01.29 |