🔎 최단 경로
최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘
'길 찾기' 문제라고도 불림
최단 경로 알고리즘 유형에는 다양한 종류가 있으며, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있음
코딩 테스트에서는 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제됨
해당 책에서는 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘 이 2가지를 다룸
🔎 다익스트라 최단 경로 알고리즘
다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘
음의 간선이 없을 때 정상적으로 동작함
그리디 알고리즘으로 분류됨 (매 상황에서 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문)
알고리즘의 동작 과정
1. 출발 노드를 설정함
2. 최단 거리 테이블을 초기화함
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택함
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신함
5. 위 과정에서 3과 4번을 반복함
알고리즘 동작 과정에서 최단 거리 테이블은 '각 노드에 대한 현재까지의 최단 거리' 정보를 가지고 있음
더 짧은 경로를 찾게되면 최단 거리 테이블을 갱신함
단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않음
- 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있음
📍 방법 1. 간단한 다익스트라 알고리즘
코드 보기
처음에 각 노드에 대한 최단 거리를 담는 1차원 리스트를 선언함
이후에 단계마다 '방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택'하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차 탐색)함
시간 복잡도 = O(V²), 총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 하고, 현재 노드와 연결된 노드를 매번 일일이 확인하기 때문
But, 노드의 개수가 10,000개가 넘어가는 문제라면 해당 코드로는 문제 해결 어려움
=> '개선된 다익스트라 알고리즘'을 이용해야 함
➕ 우선순위 큐
(방법 2에 앞서 필요한 배경지식)
힙 자료구조는 우선순위 큐를 구현하기 위하여 사용하는 자료구조 중 하나
우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
참고)
| 자료구조 | 추출되는 데이터 |
|---|---|
| 스택 | 가장 나중에 삽입된 데이터 |
| 큐 | 가장 먼저 삽입된 데이터 |
| 우선순위 큐 | 가장 우선순위가 높은 데이터 |
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용함
ex) 여러 개의 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건 데이터부터 꺼내서 확인해야 하는 경우
파이썬에서 우선순위 큐가 필요할 때 PriorityQueue 또는 heapq 사용 가능
두 라이브러리 모두 우선순위 큐 기능 지원, heapq가 더 빠르게 동작함
우선순위 큐 구현시 최소 힙과 최대 힙 이용함
최소 힙 => '값이 낮은 데이터가 먼저 삭제'
최대 힙 => '값이 큰 데이터가 먼저 삭제'
파이썬 라이브러리에서는 기본적으로 최소 힙 구조를 이용함
최소 힙을 최대 힙처럼 사용하기 위해 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여서 넣었다가 나중에 원래의 값으로 돌리는 테크닉도 기억해 놓자
📍 방법 2. 개선된 다익스트라 알고리즘
코드 보기
각 노드에 대한 최단 거리를 담는 1차원 리스트를 이용하는 것은 똑같음 (다익스트라 알고리즘이 동작하는 기본 원리는 동일)
현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가로 이용함
'최단 거리가 가장 짧은 노드'를 선택하는 과정을 다익스트라 최단 경로 함수 안에서 우선순위 큐를 이용하는 방식으로 대체'
시간 복잡도 = O(ElogV), 직관적으로 전체 과정은 E개의 원소를 우선순위 큐에 넣었다가 모두 빼내는 연산과 매우 유사함
🔎 플로이드 워셜 알고리즘
플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우'에 사용하는 알고리즘
다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행함
단, 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요 X
a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사함
점화식 => Dab = min(Dab, Dak + Dkb)
2차원 리스트에 '최단 거리' 정보를 저장함
노드의 개수가 N개일 때 N번의 단계를 수행하며, 단계마다 O(N²)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려함
따라서 플로이드 워셜 알고리즘의 시간 복잡도 = O(N³)
✏️ 실전 문제
📝 미래 도시
방문 판매원 A는 많은 회사가 보여 있는 공중 미래 도시에 있음
공중 미래 도시에는 1번부터 N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있음
방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 함
공중 미래 도시에서 특정 회사에 도착하기 위한 방법은 회사끼리 연결되어 있는 도로를 이용하는 방법이 유일함
또한 연결된 2개의 회사는 양방향으로 이동할 수 있으며, 정확히 1만큼의 시간으로 이동할 수 있음
또한 오늘 방문 판매원 A는 기대하던 소개팅에도 참석하고자 함
소개팅의 상대는 K번 회사에 존재함
방문 판매원 A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정임 (실제로 커피를 마시는 시간 등은 고려하지 않는다고 가정함)
따라서 방문 판매원 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표임
이때 방문 판매원 A는 가능한 한 빠르게 이동하고자 함
방문 판매원이 회사 사이를 이동하게 되는 최소 시간을 계산하는 프로그램을 작성하시오
- 입력 조건
- 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어짐 (1 ≤ N, M ≤ 100)
- 둘째 줄부터 M + 1번째 줄에는 연결된 두 회사의 번호가 공백으로 구분되어 주어짐
- M + 2번째 줄에는 X와 K가 공백으로 구분되어 차례대로 주어짐 (1 ≤ K ≤ 100)
- 출력 조건
- 첫째 줄에 방문 판매원 A가 K번 회사를 거쳐 X번 회사로 가는 최소 이동 시간을 출력함- 만약 X번 회사에 도달할 수 없다면 -1을 출력함
문제 해설
이 문제는 전형적인 플로이드 워셜 알고리즘 문제
문제에서 N의 범위가 100 이하로 매우 한정적임, 따라서 플로이드 워셜 알고리즘을 이용해도 빠르게 풀 수 있기 때문에 구현이 간단한 플로이드 워셜 알고리즘을 이용하는 것이 유리함
이 문제의 핵심 아이디어는 1번 노드에서 X를 거쳐 K로 가는 최단거리는 1번 노드에서 X까지의 최단 거리 + X에서 K까지의 최단 거리라는 점
소스코드
📝 전보
어떤 나라에는 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에서 보낸 메시지를 받는 도시의 총 개수와 총 걸리는 시간을 공백으로 구분하여 출력함
문제 해설
핵심 아이디어: 한 도시에서 다른 도시까지의 최단 거리 문제로 치환할 수 있으므로 다익스트라 알고리즘을 이용해서 풀 수 있음
또한 N, M의 범위가 충분히 크기에, 우선순위 큐를 이용하여 다익스트라 알고리즘을 작성해야 함
소스코드
📒 이것이 코딩 테스트다 교재를 통해 학습한 내용을 정리하였습니다.
