<본 게시글은 권오흠 교수님의 알고리즘 강의을 공부하고 정리한 글 입니다. >
[ 그래프 문제 유형 ]
● DFS / BFS
- 그래프 탐색
- DFS는 재귀와 Stack 자료구조를 이용하고 , BFS 는 Queue 자료구조를 이용한다.
- 모든 엣지의 가중치가 1이라고할때 BFS로 최단 경로를 구할 수 있다.
● MST ( Minimum Spanning Tree )
- 최소 비용으로 모든 노드를 연결하는 문제 ( 엣지의 가중치가 음수 일 수 도 있다. )
- Kruskal 과 Prim 알고리즘.
● 최단 경로
- 한 노드에서 다른 노드까지 이동하는데 드는 비용이 최소인 경로를 찾는 문제
1. Single - source ( one to all ) - Dijkstra 알고리즘, Bellman-Ford 알고리즘 - 하나의 출발 노드에서 모든 노드까지의 최단 경로를 찾는 문제.
2. Single - destination ( all to one ) - 사실상 one to all 이랑 같은 유형.
- 모든 노드에서 하나의 목적 노드까지의 최단 경로를 찾는 문제.
3. Single - pair ( one to one ) - Dijkstra 알고리즘 으로 해결.
- 주어진 한 노드에서 다른 한 목적 노드까지의 최단 경로를 찾는 문제.
- 알려진 알고리즘 중에서 최악의 경우 시간복잡도가 one to all ( Dijkstra) 보다 나은 알고리즘이 없다.
그래서 Dijkstra로 모든 노드 구하다 목적 노드 t가 나오면 search를 멈추는 방법으로 해결.
4. All - pair ( all to all ) - Floyd-warshall 알고리즘.
- 모든 노드에서 모든 노드로 가는 최단 경로를 찾는 문제.
one to all 알고리즘인 Dijkstra 알고리즘 과 Floyd-warshall 알고리즘을 알아보자.
1. single - source : ( one to all ) :: Dijkstra ( 다익스트라 )
다익스트라 알고리즘은 대표적인 음수 가중치가 없다고 가정하는 알고리즘.
-> 음수 사이클이 있으면 돌면 돌수록 작아지기 때문에 최단 경로가 정의되지 않는다.
[ 최단 경로의 기본 특성 ]
모든 노드 v ㅌ V 에 대하여
- d[v] : 시작점 s 에서 v 까지 가는데 걸리는 비용 ( distance estimate )
처음에는 d[s]=0, d[v] =INF 로 설정하고 알고리즘이 진행됨에 따라 감소해간다. 하지만 항상 d[v] >= 실제(s,v) 를 유지.
최종적으로 d[v] 는 = 실제(s,v) 가 된다.
- ㅠ[v] : s 에서 v 까지의 최단 경로상에서의 v 의 직전노드 ( predecessor )
경로를 구하기 위해서 하나씩 뒤에 따라오게 한다.
[ 기본 연산 : Relaxation ]
u -------- v 엣지(u,v) 가 있고 weight 이 2라면 d[u] =5 , d[v] =9 인 상황에서
d[v](=9) 는 >= d[u](=5) + w(u,v)(=2) 이기 때문에 갱신되어야한다.
if ( d[v] > d[u] + w(u,v) ){
d[v] = d[u] + w(u,v); // relaxation
predecessor[v] = u; // 이전 노드 저장
}[ 대부분의 single source 최단 경로 알고리즘의 기본 구조 ]
- Bellman-Ford 알고리즘과 Dijsktra 알고리즘이 공통적으로 가지고 있는 알고리즘 기본 구조이다.
[ Generic - single-Source ( G , w, s ) ]
1.
- S는 공집합 으로 시작,
- S에 속하지 않는 모든 노드 V에 대해서 d[v] = INF
- 시작 노드 s의 d[s]= 0, 만약 경로를 구하고자 한다면 ㅠ[v] = NULL 로 초기화된 배열을 만들어준다.
2. 에지들에 대한 반복적인 relaxtion. ( 아무런 변화가 없을때 까지 )
알고리즘들간의 차이는 어떤 엣지에 대해서, 어떤 순서로 relaxation을 하느냐에 있다.
1. 그럼 얼만큼 relaxation 해야 되는가? N-1 번
2. relaxation 만 해도 최단 경로가 구해지는가? YES
벨만 포드 알고리즘의 pseudo 코드
1 ~ 4 line : 벨만 포드 알고리즘
5 ~ 7 line : 음수 사이클 검출 코드.
벨만포드 알고리즘의 경우 어떤 순서로 엣지들을 relaxtion 하는지 규칙이 없다.
규칙이 없기 때문에 어떤 엣지를 먼저 relaxtion 하냐에 따라서 결과를 도출하기 전까지의 중간 값이 다르다.
그래서 worst case의 경우 어느 한 노드는 매번 갱신되야 될 수 도 있다.
하지만 다익스트라 알고리즘은
매번 랜덤한 엣지에 대해서 relax 하지 않고 특별한 조건을 만족하는 엣지 들에만 relax 한다.
이러한 점에서 다익스트라 알고리즘이 더 좋다고 할 수 있다.
결과적으로 두 알고리즘의 최종 결과는 동일하다.
| Bellman - Ford | Dijkstra | |
| Time Complexity | O ( NM ) | 보통 : O(N^2) 우선순위 큐 사용 : O( NlogN+ mlogN ) |
[ 다익스트라 알고리즘 ]
1. 초기화 d[s]= 0, d[v] = INF, ㅠ[v] = NULL
2. 에지들에 대한 반복적인 relaxtion. ( 모든 노드가 집합 S에 포함될때까지 )
- 현재 노드의 인접한 노드들 relaxationn
- distance의 값이 최소인 노드를 선택하고 위의 과정 반복.
- 처음에는 출발 노드의 d[s] = 0 이기 때문에 출발 노드의 엣지들만 relax 한다.
- distance의 값이 최소인 노드 가 현재 집합 S에 속한 노드로부터 노드 u까지의 최단 경로라는 정리의 증명.
[ 기본 구현 ] - BOJ 1753 문제.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using std::cin;
using std::vector;
// 최단 경로 문제 single source (one to all) 문제
// 다익스트라 풀이
// 1. 출발 노드를 제외하고 모두 d[v] = INF, d[s]=0;
// 2. 값이 가장 작은 노드의 나가는 엣지의 최소 엣지 relaxation.
// 3. 노드가 전부 선택 될때까지 반복.
const int INF = 987654321;
int v,e, k;
int start, t, w;
vector<vector<std::pair<int,int>>> edge;
vector<int> node;
vector<int> s;
int answer[20001];
void Dijkstra(int k) {
// 초기화
std::fill_n(node.begin()+1, k-1, INF);
std::fill_n(node.begin()+ k + 1, v - k, INF);
node[k] = 0;
while (s.size() < v) { // 노드의 개수랑 같으면.
int min = std::min_element(node.begin()+1, node.end()) - node.begin();
int x = *std::min_element(node.begin() + 1, node.end());
s.push_back(min);
answer[min] = x;
for (int i = 0; i < edge[min].size(); i++) {
int next = edge[min][i].first;
auto itr = std::find(s.begin(), s.end(), next);
if (itr == s.end()) {
if (node[next] > node[min] + edge[min][i].second) {
node[next] = node[min] + edge[min][i].second;
}
}
}
node[min] = INF + 1;
}
for (int i = 1; i <= v; i++) {
if (answer[i] == INF) {
std::cout << "INF" << '\n';
}
else {
std::cout << answer[i] << '\n';
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> v >> e; // 노드 개수, 간선 개수
edge.resize(v+1);
s.reserve(v+1);
node.resize(v+1);
cin >> k; // 시작 노드 번호
for (int i = 0; i < e; i++) {
cin >> start >> t >> w;
edge[start].push_back(std::make_pair(t, w));
}
Dijkstra(k);
return 0;
}
우선 순위 큐를 사용하지 않고 Dijkstra 알고리즘을 구현할 경우 O(n^2) 의 시간복잡도를 가지기 때문에 시간초과가 나온다.
BOJ 1753 문제는 최대 노드의 개수가 10,000개를 넘어가기 때문에 10,000 ^2 인 100,000,000 ,1억 번의 연산을 넘어가게 된다.
보통 코팅테스트에서 1초를 기준으로 1억번의 연산을 마지노선으로 잡고있기 때문에, 우선 순위 큐를 사용하지 않고서는 제 시간에 문제를 풀 수 없게 된다.
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using std::cin; using std::cout;
using std::vector;
int v, e, k;
int start, end, w;
const int INF = 987654321;
vector<vector<std::pair<int, int>>> edge;
// vector<pair<int,int>> edge[20001]; <<< 이렇게 해줘도 된다.
int d[20001];
struct cmp { // priority queue 를 오름 차순으로 하기위해
bool operator()(std::pair<int,int> a ,std::pair<int,int> b ){
return a.second > b.second;
}
};
void Dijkstra(int start) {
std::priority_queue<std::pair<int,int>,vector<std::pair<int,int>>,cmp> pq;
d[start] = 0; // 시작점의 d[] 0으로
pq.push(std::make_pair(start, 0));
while (!pq.empty()) {
int cur =pq.top().first;
int d_cur = pq.top().second;
pq.pop();
// 현재 노드가 이미 처리된 적 있는 노드면 다음 노드.
if (d[cur] < d_cur)continue; // <<<<< 여기가 중요.
for (int i = 0; i < edge[cur].size(); i++) {
int next = edge[cur][i].first;
int next_dist = edge[cur][i].second;
if (d[next] > d[cur] + next_dist) {
d[next] = d[cur] + next_dist;
pq.push(std::make_pair(next, d[next]));
}
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr); std::cout.tie(nullptr);
cin >> v >> e >> k;
edge.resize(v+1);
std::fill_n(d + 1, v, INF);
for (int i = 0; i < e; i++) {
cin >> start >> end >> w;
edge[start].push_back(std::make_pair(end, w));
}
Dijkstra(k);
for (int i = 1; i <= v; i++) {
if (d[i] == INF) {
cout << "INF" << '\n';
}
else {
cout << d[i] << '\n';
}
}
return 0;
}
강조하고 싶은 부분은
// 현재 노드가 이미 처리된 적 있는 노드면 다음 노드.
if (d[cur] < d_cur)continue;
이 부분이다.
처음에는 왜 해줘야 되나 싶었다.
결국 저 코드의 이유는 pq에는 노드가 relax 되면서 담기게 되는데, 처음에 relax 되서 담긴 노드보다 작은 distance 값으로 갱신 되었을때 기존의 distance 값은 우선 순위큐 순위에 밀릴경우 큐에 남아 있게 된다.
이러한 노드를 위해 저 코드를 작성하는것이다.
예를 들면 2번 노드가 큐에 pair{ 2 , 5 } 인 상태로 들어왔는데 다른 노드에 의해 2번 노드가 다시 relax 되면서 새로운 distance 값으로 갱신되어 pair{ 2 ,4 } 로 들어오게되는 경우를 말한다.
이럴 경우 굳이 큐에 담겨있는 { 2, 5 } 를 보지 않아도 되기 때문에 continue 를 해준다.
백준 최단 경로 문제 : https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가
www.acmicpc.net
경로 출력은 predecessor에 전 노드를 업데이트 하다가
마지막에 predecessor 배열을 재귀나 스택으로 출력해주면 된다.
'CS > Algorithm' 카테고리의 다른 글
| Back Tracking (0) | 2021.11.27 |
|---|---|
| 최단 경로 ② ( Floyd - Warshall ) (0) | 2021.11.17 |
| Kruskal ( Union - Find ) (0) | 2021.11.12 |
| MST ( Minimum Spanning Tree ) - Kruskal , Prim (0) | 2021.11.11 |
| BFS ( Breadth First Search ) (0) | 2021.11.10 |