🔵 다익스트라 알고리즘
출발 노드에서 그래프 내의 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다.
간선의 가중치가 음수가 아니어야 하며, 일반적으로 단일 출발점 최단 경로 문제를 해결할 때 사용된다.
다익스트라 알고리즘은 기본적으로 그리디 방식으로 작동한다.
- 시작 노드로부터 거리를 모두 무한대로 초기화한다. (단 시작 노드 자신까지의 거리는 0으로 설정한다.)
- 아직 방문하지 않은 노드들 중에서, 시작 노드로부터의 거리가 가장 짧은 노드를 선택한다.
- 선택된 노드를 방문 처리하고, 이제 그 노드까지의 최단 거리는 확정된 것으로 간주한다.
- 선택된 노드를 경유하여 인접한 다른 노드들로 갈 때의 거리를 계산하고, 현재까지 알려진 그 노드까지의 최단거리와 비교하여 더 짧으면 갱신한다.
- 이 과정을 모든 노드를 방문할 때까지 반복한다.
🔷 구현 방식 - 인접 행렬
노드의 수가 적고 (1000 이하) 간선이 많은 밀집 그래프에 적합하고, 간편하게 구현할 수 있다.
특정 간선의 존재 여부를 매우 빠르게 확인할 수 있기 때문에(O(1)), 두 노드 간 연결 여부를 자주 확인해야 하는 문제에는 이 방식이 적합하다.
노드의 개수를 N, 간선의 개수를 E라고 할 때, 시간 복잡도는 O(N^2)이다.
그래프는 배열로 표현한다.
x와 y 사이 가중치가 3이라는 간선이 있다고 가정했을 때, graph[x][y] = 3 으로 표현한다.
#include <string>
#include <vector>
#include <tuple>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
const int MAX_NODES = 100;
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];
vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>> edges)
{
// 그래프 및 방문 여부 초기화
for (int i = 0; i < MAX_NODES; i++)
{
fill_n(graph[i], MAX_NODES, INF);
visited[i] = false;
}
// 입력받은 간선 정보를 그래프로 표현
for (const auto& [from, to, weight] : edges)
{
graph[from][to] = weight;
}
// 시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
vector<int> distances(numNodes, INF);
// 시작 노드로부터 특정 노드까지의 확정된 최단 거리
distances[start] = 0;
for (int i = 0; i < numNodes - 1; i++)
{
int minDistance = INF;
int closestNode = -1;
// 최소 거리 노드 찾기
// 우선 순위 큐처럼 동작
for (int j = 0; j < numNodes; j++)
{
if (!visited[j] && distances[j] < minDistance)
{
minDistance = distances[j];
closestNode = j;
}
}
// 예외 발생 시 정지
if (closestNode == -1) break;
// 찾은 노드를 방문 처리
visited[closestNode] = true;
// 인접 노드에 대한 거리 업데이트
for (int j = 0; j < numNodes; j++)
{
int newDistance = distances[closestNode] + graph[closestNode][j];
if (!visited[j] && graph[closestNode][j] != INF && newDistance < distances[j])
distances[j] = newDistance;
}
}
return distances;
}
위 코드에서 우선 순위 큐처럼 동작하는 부분을 실제 우선 순위 큐로 구현하지 않은 이유가 있다.
우선 순위 큐로 했을 때 얻을 수 있는 이점은 시간 복잡도에서의 이점인데, 코드 마지막 for문의 영향으로 어차피 시간 복잡도에 큰 이점이 없어지기 때문에 비교적 간단한 구현으로 처리하였다.
🔷 구현 방식 - 인접 리스트 & 우선순위 큐
노드의 수가 많고, 간선의 수가 적은 희소 그래프에 특히 적합하다. 구현이 인접 행렬보다 약간 복잡할 수 있지만, 특별한 경우가 아니라면 전체 시간 복잡도가 O(V+E), 또는 O(ElogV) 등으로 훨씬 효율적이다.
vector<vector<pair<int, int>>> 형식으로 그래프를 표현한다.
x와 y 사이 가중치가 3이라는 간선이 있다고 가정했을 때, graph[x]에는 pair<int, int> 형식으로 {y, 3}이 들어있다.
#include <string>
#include <vector>
#include <tuple>
#include <limits>
#include <queue>
using namespace std;
const int INF = numeric_limits<int>::max();
struct Compare
{
bool operator()(const pair<int, int>& a, const pair<int, int>& b)
{
return a.first > b.first; // 거리가 작은 순대로 정렬
}
};
vector<int> solution(int start, int numNodes, vector<tuple<int, int, int>> edges)
{
// 간선 정보를 활용해서 인접 리스트를 생성
vector<vector<pair<int, int>>> adjList(numNodes);
for (const auto& [from, to, weight] : edges)
// emplace_back: 객체 생성에 필요한 인자만 받은 후 함수 내에서 객체를 생성해 삽입한다.
adjList[from].emplace_back(to, weight);
// 시작 노드를 제외한 모든 노드의 최소 비용을 INF로 초기화
vector<int> distances(numNodes, INF);
distances[start] = 0;
// 우선순위 큐에 시작 노드 추가
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
pq.push({ 0, start });
// 노드의 방문 여부를 저장하는 배열
vector<bool> visited(numNodes, false);
while (!pq.empty())
{
int currentDistance = pq.top().first;
int currentNode = pq.top().second;
pq.pop();
// 이미 방문한 노드인 경우 무시
if (visited[currentNode]) continue;
// 현재 노드를 방문 처리
visited[currentNode] = true;
// 인접 노드에 대한 거리 업데이트
for (const auto& [neighbor, weight] : adjList[currentNode])
{
int newDistance = distances[currentNode] + weight;
if (newDistance < distances[neighbor])
{
distances[neighbor] = newDistance;
pq.push({ newDistance, neighbor });
}
}
}
return distances;
}
🔹 Compare를 왜 함수 포인터 대신 구조체로 선언하였는가?
struct Compare
{
bool operator()(const pair<int, int>& a, const pair<int, int>& b)
{
return a.first > b.first; // 거리가 작은 순대로 정렬
}
};
C++에서 비교자를 정의하는 방법은 크게 함수 포인터, 함수 객체, 람다 표현식이 있다.
priority_queue의 비교자는 함수 객체 혹은 람다 타입이어야 한다.
따라서 비교자를 struct로 구현했다.
🔹 emplace_back은 무엇인가?
for (const auto& [from, to, weight] : edges)
adjList[from].emplace_back(to, weight);
push_back과 유사하게 컨테이너 끝에 요소를 추가하는 역할을 한다.
push_back은 완전히 구성된 객체를 받아서 컨테이너에 추가한다.
emplace_back은 객체로 생성하는 데 필요한 인자들을 직접 받는다. 그리고 컨테이너 내부에서 해당 인자들을 사용하여 객체를 그 자리에서 바로 생성한다.
🔹 우선순위 큐 선언
// priority_queue< ElementType, ContainerType, ComparatorType > variableName;
priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
ElementType
우선순위 큐에 저장될 요소의 타입
ContainerType
우선순위 큐가 내부적으로 요소를 저장하고 관리하는 데 사용할 기반 컨테이너의 타입.
기본값은 std::vector이므로 이 코드에서는 이 부분을 명시적으로 지정하지 않아도 된다.
ComparatorType
우선순위 큐 내부에서 두 요소를 비교하여 어떤 것이 더 높은 우선순위를 가지는지 결정하는 비교자 타입(함수 객체 혹은 람다).
🔵 벨만-포드 알고리즘
다익스트라 알고리즘과 비슷하게 단일 출발점 최단 경로를 찾는 알고리즘이다.
가장 중요한 특징은 다음과 같다.
- 음수 가중치 간선이 있는 그래프에서 최단 경로를 찾을 수 있다.
- 음수 가중치 사이클을 감지할 수 있다.
음수 가중치 사이클이란 경로를 따라가면 총 비용이 계속 감소하는 사이클이다.
이 사이클이 존재하면 최단 경로가 무한히 작아질 수 있으므로, 최단 경로가 정의되지 않는다.
벨만-포드 알고리즘은 DP 원리를 사용하여 최단 경로를 찾는다.
다익스트라가 가장 가까운 노드를 찾아 확정하는 탐욕적인 방식이라면, 벨만-포드는 모든 간선을 여러 번 이완하여 점진적으로 최단 경로를 찾아가는 방식이다.
(Relaxation(이완)이란, 현재까지 알려진 어떤 노드까지의 최단 거리가 있을 때, 더 짧은 경로를 발견해 이를 갱신하는 과정을 말한다.)
- 시작점을 설정한다.
- 모든 간선을 (V - 1)번 반복해서 이완한다. (최단 경로는 사이클이 없는 한 최대 V - 1개의 간선으로 이루어진다.)
- 마지막으로 한 번 더 모든 간선을 이완해 보고, 이때도 갱신이 발생하면 음수 사이클이 있음을 확정한다.
- 결과를 반환한다.
#include <string>
#include <vector>
#include <tuple>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
vector<int> solution(int num_vertices, vector<tuple<int, int, int>> edges, int source)
{
vector<vector<pair<int, int>>> graph(num_vertices);
// 간선 정보를 활용해서 인접 리스트 생성
for (auto& [from, to, weight] : edges)
graph[from].emplace_back(to, weight);
// 현재까지 구한 최소 비용을 INF로 설정
// 시작 노드 설정
vector<int> distances(num_vertices, INF);
distances[source] = 0;
// 정점의 개수 - 1 만큼 최소 비용 갱신
for (int i = 0; i < num_vertices - 1; i++)
{
for (int u = 0; u < num_vertices; u++)
{
for (const auto& [v, weight] : graph[u])
{
if (distances[u] + weight < distances[v])
distances[v] = distances[u] + weight;
}
}
}
// 음의 순환이 있는지 확인
for (int u = 0; u < num_vertices; u++)
{
for (const auto& [v, weight] : graph[u])
{
if (distances[u] + weight < distances[v])
// 음의 순환 발견
return vector<int>(1, -1);
}
}
return distances;
}
노드의 개수를 N, 간선의 개수를 E라 할 때, 노드의 개수만큼 최단 경로를 갱신하는 연산을 하므로 시간 복잡도는 O(N*E)이다.
벨만-포드 알고리즘은 다익스트라 알고리즘과는 달리 음수 가중치가 있다고 가정하므로 한 번의 선택으로 최단 거리가 확정될 수 없다고 본다.
이전 반복에서 발생한 distances 값 변화를 기반으로, 아직 발견되지 않은 더 짧은 경로를 찾아내기 위해 모든 간선을 다시 한번 재검토하고 정보가 충분히 전파되게 한다.
따라서 모든 간선을 여러 번(V - 1)번 반복하여 모든 경로가 충분히 이완될 기회를 준다.
'PS' 카테고리의 다른 글
| [C++] Programmers Lv. 2 "게임 맵 최단거리" (0) | 2025.06.11 |
|---|---|
| [C++] Programmers Lv. 2 "미로 탈출" (0) | 2025.06.10 |
| [C++] Programmers Lv. 3 "섬 연결하기" (0) | 2025.06.05 |
| [C++] Programmers Lv. 1 "폰켓몬" (0) | 2025.06.05 |
| [C++] Programmers Lv. 3 "길 찾기 게임" (0) | 2025.06.04 |