반응형
BFS와 다익스트라는 최단거리를 구한다는 점에서 의미가 동일하다.
그렇다면 언제 BFS를 쓰고, 언제 다익스트라를 써야할까?
BFS는 간선 간의 거리가 모두 같을 때 사용하며, 다익스트라는 간선 간의 거리가 다를 때 사용한다.
주의해야할 점은, 다익스트라 특성상 간선이 음수일 경우에는 알고리즘이 적용될 수 없다.
다익스트라 코드를 보면 크게 두 가지 부류가 있다
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> pii;
void dijkstra(int start, vector<vector<pii>>& graph, vector<int>& distance) {
int n = graph.size();
priority_queue<pii, vector<pii>, greater<pii>> pq;
distance.assign(n, INT_MAX);
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int current_node = pq.top().second;
int current_distance = pq.top().first;
pq.pop();
if (current_distance > distance[current_node]) {
continue;
}
for (const auto& neighbor : graph[current_node]) {
int neighbor_node = neighbor.first;
int new_distance = current_distance + neighbor.second;
if (new_distance < distance[neighbor_node]) {
distance[neighbor_node] = new_distance;
pq.push({new_distance, neighbor_node});
}
}
}
}
이런 류와
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> pii;
void dijkstra(int start, vector<vector<pii>>& graph, vector<int>& distance) {
int n = graph.size();
priority_queue<pii, vector<pii>, greater<pii>> pq;
distance.assign(n, INT_MAX);
distance[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int current_node = pq.top().second;
int current_distance = pq.top().first;
pq.pop();
for (const auto& neighbor : graph[current_node]) {
int neighbor_node = neighbor.first;
int new_distance = current_distance + neighbor.second;
if (new_distance < distance[neighbor_node]) {
distance[neighbor_node] = new_distance;
pq.push({new_distance, neighbor_node});
}
}
}
}이런 류이다. 결론적으로 보자면 딱 한 군데만 다르다!
바로 아래 코드가 있고 없고의 차이이다.
if (current_distance > distance[current_node]) {
continue;
}
우선순위 큐 기반으로 구현하는 다익스트라 알고리즘에 대해서 우선 간단히 설명하자면
노드를 선택하고, 인접한 노드들을 살펴본 뒤에 거리값을 더 단축시키게 갱신할 수 있다면
갱신한 뒤에 우선순위 큐에 넣어준다.
말 그대로 거리값이 더 단축시키게 갱신된다면, 우선순위 큐 안에는 같은 노드라도 거리가 다른 노드들이 여러개 있을 수 있다.
{거리, 노드} 라면
처음 넣었을 때
{6, 1}
나중에 갱신하여
{3, 1}
이렇게 중복되어 있더라도, 어차피 최대힙 최소힙 기반이고, 결국엔 큰 의미는 없는 for 반복문으로 코드가 끝이 나겠지만
for (const auto& neighbor : graph[current_node])
이마저도 그냥 종료시키고 싶다면 if문을 넣어서 분기를 처리해주는 것이다!
있으나 없으나 코드의 결과는 똑같다.
다익스트라를 공부하기에도 벅차겠지만, 다익스트라를 응용한 문제를 하나 가져왔다!
"프로그래머스 등산 코스 정하기"
이는 누적으로 구하는 다익스트라 방식은 아니지만, 각 간선을 움직일 때마다 각 간선이 최소이기만 하면 된다.
이 또한 간선의 길이가 있고, 최소 값을 이용한다는 점에서 다익스트라를 응용하여 풀이할 수 있다.
#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#define MAX(a,b) ((a >= b) ? a : b)
using namespace std;
vector<vector<pair<int, int>>> v(50001, vector<pair<int, int>>());
vector<pair<int, int>> ans;
void dijkstra(int n, vector<int>& gates, vector<int>& summits) {
vector<int> distance(n + 1, -1);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(auto gate : gates) {
distance[gate] = 0;
pq.push({0, gate});
}
while(!pq.empty()) {
int node_distance = pq.top().first;
int node = pq.top().second;
pq.pop();
if(find(summits.begin(), summits.end(), node) != summits.end()) {
ans.push_back({node_distance, node});
continue;
}
for(int i = 0; i < v[node].size(); i++) {
int maxD = MAX(node_distance, v[node][i].second);
// 다익스트라랑 똑같은 역할의 분기문
// 다익스트라는 누적값이라 이걸 하나의 if문으로 해결 가능함 (Dist[Next] > Cost + nCost)
// -1 : 이미 방문한 노드 안돌아봄, < : 해당 노드 이미 더 짧은 경로로 갈 수 있으면 안감. 최단경로 갱신이니까.
if(distance[v[node][i].first] == -1 || maxD < distance[v[node][i].first]) {
pq.push({maxD, v[node][i].first});
distance[v[node][i].first] = maxD;
}
}
}
}
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
vector<int> answer;
for(auto path : paths) {
v[path[0]].push_back({path[1], path[2]});
v[path[1]].push_back({path[0], path[2]});
}
dijkstra(n, gates, summits);
sort(ans.begin(), ans.end());
return {ans[0].second, ans[0].first};
}난 이 문제를 푸느라 하루 종일이 걸렸다..
특이한 점은, 다익스트라나 다익스트라 응용이나 BFS처럼 visit을 따로 사용하지 않고 거리 값 갱신에 따른 조건문으로 이를 대체한다는 점.
또 다시 풀었다. 역시나 잊고 있었지만, 다익스트라나 다익스트라 응용은 BFS처럼 visit으로 방문처리를 사용하지 않고 거리 값 갱신에 따른 조건문으로 이를 대체한다. 나는 다익스트라를 활용하지 못하고 BFS의 느낌으로 다시 풀었네.
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <queue>
#define MAX(a,b) ((a>=b)?a:b)
using namespace std;
bool visit[50001];
int max_interval = 0;
set<pair<int, int>> answer;
void pq(vector<int> gates, vector<int> summits, int n, vector<vector<pair<int, int>>>& v) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(auto gate: gates) {
pq.push({0, gate});
}
while(!pq.empty()) {
int interval = pq.top().first;
int node = pq.top().second;
pq.pop();
if(visit[node]) continue;
visit[node] = true;
max_interval = MAX(max_interval, interval);
if(find(summits.begin(), summits.end(), node) != summits.end()) {
answer.insert({max_interval, node});
continue;
}
for(int i = 0; i < v[node].size(); i++) {
int new_node = v[node][i].first;
int new_interval = v[node][i].second;
if(!visit[new_node]) pq.push({new_interval, new_node});
}
}
}
vector<int> solution(int n, vector<vector<int>> paths, vector<int> gates, vector<int> summits) {
vector<vector<pair<int, int>>> v(n + 1, vector<pair<int, int>>());
for(const auto& path: paths) {
v[path[0]].push_back({path[1], path[2]});
v[path[1]].push_back({path[0], path[2]});
}
pq(gates, summits, n, v);
return {(*answer.begin()).second, (*answer.begin()).first};
}
/*
다시 풀어본 결과
다익스트라에서는 push와 동시에 visit처리를 하지 않는다. 꺼낼 때 처리한다.
그리고 조건 분기문이 2개가 되었는데 이게 맞나.
*/
다익스트라로 다시 풀어봐야겠다.
참고
https://yabmoons.tistory.com/364
반응형
'[알고리즘 + 자료구조]' 카테고리의 다른 글
| [알고리즘] Floyd Warshall (0) | 2022.10.26 |
|---|---|
| C++ 2차원 배열 회전하기 (0) | 2022.10.06 |
| [C++] 정규표현식, 정규식 유형 알아보기 (1) | 2022.09.29 |
| BFS depth 계산 (0) | 2021.10.08 |
| [알고리즘] CCW (0) | 2021.09.29 |
