최단 경로
"가장 짧은 경로를 찾는 알고리즘"
✔ '길 찾기' 문제 혹은 '가장 짧은 경로를 찾는' 문제라고 불립니다.
✔ 보통 Graph를 이용해 표현합니다.
✔ 실제 코테에서는 단순히 최단 거리를 출력하도록 요구하는 문제가 출제된다.
✔✔ Greedy와 DP의 한 유형이라고 할 수 있습니다.
🌈 최단 경로 알고리즘 종류
① 다익스트라 최단 경로 알고리즘 ***
② 플로이드 워셜 알고리즘 ***
③ 벨만 포드 알고리즘
🏇 다익스트라 최단 경로 알고리즘
"여러 개의 노드 중, 특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구하는 알고리즘"
✔ 0보다 작은 값의 간선이 없을 때, 정상적으로 실행이 가능합니다.
✔ 매번 가장 작은 비용의 노드를 선택하는 과정을 반복하기 때문에 'Greedy'로 분류됩니다.
🐸 실행 과정
① 출발 노드를 설정한다.
② 최단 거리 테이블*을 초기화한다.
③ 방문하지 않은 노드 중, 최단 거리가 가장 짧은 노드를 선택한다.
④ 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 갱신한다.
⑤ 위 과정에서③, ④를 반복한다.
|
최단 거리 테이블이란? |
✔ 아래의 방법을 반복합니다.
 ✔ 초기 상태에는 거리를 무한으로 초기화합니다. ✔ 출발 노드인 1의 거리는 0입니다.(자기 자신에서 출발하므로) |
 ✔ 노드 1에서 이동할 수 있는 방법은 총 세 가지입니다. |
** 그림의 테이블에는 노드 6이 빠져있습니다. 그리다보니 빼먹음...
암튼 출발부터 가장 최단 거리를 선택해 거리를 계산하므로 마지막 노드는 확인할 필요가 없습니다.
| 방법 1. 간단한 알고리즘
⏱ 간단한 다익스트라 알고리즘의 시간복잡도
: Θ(V^2)
* 이때 V는 노드의 개수
🐸 실행 과정
✔ 처음에는 1차원 배열을 선언.
✔ 단계마다 '방문하지 않는노드 중, 최단 거리가 가장 짧은 노드를 선택'하기 위해 단계마다 1차원 리스트를 순차 탐색(원소를 모두 확인)
💻 코드 예시
** 전체 노드의 개수가 5,000개 이하일 때,
#include <iostream>
#include <vector>
using namespace std;
/*
*코드 참고 : https://github.com/ndb796/python-for-coding-test/blob/master/9/1.cpp
*/
// 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
int n, m, start;
vector<pair<int, int>> graph[100001]; // 노드 정보 저장
bool visited[100001]; // 방문 check
int d[100001]; // 최단 거리 테이블
// 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
int getSmallNode(){
int min_value = 1e9;
int index = 0;
for(int i = 0; i <= n; i++){
if(d[i] < min_value && !visited[i]){
min_value = d[j];
index = i;
}
}
return index;
}
void dijkstra(int start){
// 시작 노드 초기화 & 방문처리
d[start] = 0;
visited[start] = true;
for(int i = 0; i < graph[start].size(); i++){
d[graph[start][i].first] = graph[start][i].second;
}
// 시작 노드 제외한 전체 n - 1까지 반복
for(int i = 0; i < n - 1; i++){
// 현재 최단 거리 짧은 노드 꺼내서 방문처리
int now = getSmallNode();
visited[now] = true;
// 현재 노드와 연결된 다른 노드 확인
for(int j = 0; j < graph[now].size(); i++){
int cost = d[now] + graph[now][j].second;
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if(cost < d[graph[now][j].first]) d[graph[now][j]].first = cost;
}
}
}
int main() {
cin >> n >> m >> start;
// 간선 정보 입력
for(int i = 0; i < n; i++){
int a, b, c;
cin >> a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back({b, c});
// graph[a].push_back(make_pair(b, c)); 도 가능하당
}
d[100001] = {1e9,}; // 무한 초기화
// 다익스트라 수행
dijkstra(start);
for(int i = 1; i <= n; i++){
if(d[i] != 1e9) cout << d[i] << endl;
}
return 0;
}
| 방법 2. 개선된 알고리즘
⏱ 간단한 다익스트라 알고리즘의 시간복잡도
: 최악의 경우에도 Θ(E log V)
* 이때 E는 간선의 개수, V는 노드의 개수
✔ Heap 이용 : 보러가기
🐸 실행 과정
✔ 처음에는 1차원 배열을 선언.
✔ 단계마다 '방문하지 않는노드 중, 최단 거리가 가장 짧은 노드를 선택'하기 위해 단계마다 1차원 리스트를 순차 탐색(원소를 모두 확인)
✔ ✔ 현재 가장 가까운 노드를 저장하기 위한 목적으로만 우선순위 큐를 추가 이용합니다.
✔ 아래의 방법을 반복합니다.
|
+) 우선순위 큐 (거리 : 1, 노드 : 4) (거리 : 2, 노드 : 2) (거리 : 5, 노드 : 3) |
💻 코드 예시
** 전체 노드의 개수가 5,000개 이하일 때,
**** getSmallNode( )함수를 구현할 필요가 없다.
최단 거리의 노드를 선택할 때, 우선 순위 큐를 이용하면 되기 때문.
***** C++의 priority_queue의 경우 "최대 힙"으로 우선 순위가 구현되어 있기 때문에 최소 힙으로 구현하기 위해서는 -를 붙여준다.
int dist = -pq.top().first;
pq.push(make_pair(-cost, graph[now][i].fisrt));#include <iostream>
#include <vector>
#include <priority_queue>
using namespace std;
/*
* 코드 참고 : https://github.com/ndb796/python-for-coding-test/blob/master/9/2.cpp
*/
int n, m, start;
vector<pair<int, int>> graph[100001];
int d[100001]; // 최단 거리 테이블
void dijkstra(int start){
priority_queue<pair<int, int>> pq;
// 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
pq.push({0, start});
d[start] = 0;
while(!pq.empty()){
// 가장 최단 거리 짧은 노드 꺼내기
int dist = -pq.top().first; // 현재 노드의 비용
int now = pq.top().second; // 현재 노드
pq.pop();
if(d[now] < dist) continue; // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
for(int i = 0; i < graph[now].size(); i++){
int cost = dist + graph[now][i].second();
// 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
if(cost < d[graph[now][j].first]){
d[graph[now][i].first] = cost;
pq.push(make_pair(-cost, graph[now][i].fisrt));
}
}
}
}
int main() {
cin >> n >> m >> start;
// 모든 간선 정보를 입력받기
for(int i = 0; i < m; i++){
int a, b, c;
cin a >> b >> c;
// a번 노드에서 b번 노드로 가는 비용이 c라는 의미
graph[a].push_back(make_pair(b, c));
}
d[100001] = {1e9,};
dijkstra(start);
for(int i = 1; i <= n; i++){
if(d[i] != 1e9) cout << d[i] << " ";
}
return 0;
}
🏇 플로이드 워셜 알고리즘
"모든 지점에서 다른 모든 지점까지이 최단 경로를 모두 구해야 하는 경우 사용하는 알고리즘"
✔ 단계마다 '거쳐가는 노드 기준'으로 알고리즘 수행
BUT 매번 방문 X 노드는 찾을 필요가 없다.
✔ 2차원 리스트에 최단 거리 정보 저장
✔ 노드가 N개일 때, N번만큼 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 'DP'로 분류됩니다.
✔ ✔ 3중 반복문으로 점화식에 따라 2차원 리스트를 갱신하면 됩니다.
⏱ 시간복잡도
: Θ(N^3)
🐸 실행 과정
💻 코드 예시
#include <iostream>
#include <vector>
using namespace std;
// 노드 개수는 최대 500개라고 가정한다.
// 노드 개수 n, 간선 개수 m
int n, m;
int graph[501][501]; // 최단 거리 테이블
int main() {
cin >> n >> m;
// 최단 거리 테이블 무한으로 초기화
for(int i = 0; i < 501; i++){
for(int j = 0; j < 501; j++){
graph[i][j] = 1e9;
}
}
// 자기 자신에서 자기 자신으로 가는 거리는 0
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i == j) graph[i][j] = 0;
}
}
// 각 간선 정보 입력 받기
for(int i = 0; i < m; i++){
int a, b, c; // A에서 B로 가는 비용은 C라고 설정
cin >> a >> b >> c;
graph[a][b] = c;
}
// 점화식에 따라 플로이드 워셜 알고리즘 수행
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
//결과 출력
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(graph[i][j] != ) cout << graph[i][j];
}
cout << endl;
}
return 0;
}
// 코드 참고 : https://github.com/ndb796/python-for-coding-test/blob/master/9/3.cpp
🌷 문제
이것이 취업을 위한 코딩 테스트다
유형 1 - 미래 도시
유형 2 - 전보
'OLD_알고리즘' 카테고리의 다른 글
| Solving Skill ] 완전 탐색 (0) | 2021.04.16 |
|---|---|
| 완탐中 ] 순열과 조합 (0) | 2021.04.16 |
| 자료구조 ] Heap 자료구조 (0) | 2021.03.22 |
| Solving Skill ] 다이나믹 프로그래밍(DP) (0) | 2021.03.16 |
| Solving Skill ] 이진 탐색 (0) | 2021.03.10 |
댓글