작성자: [조광형]
날짜: [날짜]
1. 개요
코딩테스트는 소프트웨어 개발 직군에 지원함에 있어 필수적으로 요구되는 과정입니다. 많은 기업들이 다양한 알고리즘 문제를 통해 지원자의 문제해결 능력을 평가하고, 이를 위해 벨만-포드 알고리즘을 이해하고 활용하는 능력이 중요합니다. 본 강좌에서는 벨만-포드 알고리즘을 소개하고, C++를 이용하여 실습해보겠습니다.
2. 알고리즘 소개
벨만-포드 알고리즘(Bellman-Ford Algorithm)은 주어진 출발점에서 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 음의 가중치를 가진 간선을 포함한 그래프에서도 최단 경로를 찾을 수 있도록 설계되었습니다. 따라서, 벨만-포드 알고리즘은 다익스트라 알고리즘과 달리 음의 가중치를 처리할 수 있는 중요한 알고리즘입니다.
벨만-포드 알고리즘의 핵심 아이디어는 다음과 같습니다:
- 모든 간선을 반복적으로 검사하여 최단 경로를 업데이트합니다.
- 모든 정점에 대한 출발점으로부터의 최단 거리를 저장합니다.
- 최대 (정점 수 – 1) 번의 반복 후에도 경로가 업데이트된다면, 음의 사이클이 존재하는 것입니다.
3. 문제 설명
다음과 같은 문제를 통해 벨만-포드 알고리즘을 이해해보겠습니다.
문제: N개의 도시가 있고, M개의 도로가 있습니다. 각 도로는 두 도시 A, B와 가중치 C로 표현됩니다. 한 도시에서 출발하여 모든 도시로 갈 수 있는 최단 경로의 가중치를 출력하세요. 길이 존재하지 않거나, 음의 사이클이 존재하는 경우 “Impossible”을 출력해야 합니다.
입력 형식
- 첫 번째 줄에 N (도시의 수)과 M (도로의 수)이 주어진다.
- 다음 M개의 줄에 각 도로의 정보 A, B, C가 주어진다.
출력 형식
- 출발점에서 각 도시까지의 최단 거리 혹은 “Impossible”의 결과를 출력한다.
4. 알고리즘 구현
이제 C++를 사용하여 벨만-포드 알고리즘을 구현해보겠습니다. 다음은 문제를 해결하기 위한 코드입니다:
#include <iostream>
#include <vector>
#include <limits>
using namespace std;
struct Edge {
int u, v, weight;
};
void bellmanFord(int V, int E, vector<Edge> &edges, int start) {
// 최단 거리 초기화
vector<double> distance(V, numeric_limits<double>::infinity());
distance[start] = 0;
// V-1 회 반복
for (int i = 1; i < V; i++) {
for (const auto &edge : edges) {
if (distance[edge.u] != numeric_limits<double>::infinity() &&
distance[edge.u] + edge.weight < distance[edge.v]) {
distance[edge.v] = distance[edge.u] + edge.weight;
}
}
}
// 음의 사이클 체크
for (const auto &edge : edges) {
if (distance[edge.u] != numeric_limits<double>::infinity() &&
distance[edge.u] + edge.weight < distance[edge.v]) {
cout << "Impossible" << endl;
return;
}
}
// 결과 출력
for (int i = 0; i < V; i++) {
if (distance[i] == numeric_limits<double>::infinity()) {
cout << "INF" << endl;
} else {
cout << distance[i] << endl;
}
}
}
int main() {
int N, M;
cin >> N >> M;
vector<Edge> edges(M);
for (int i = 0; i < M; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].weight;
}
int start = 0; // 출발점을 0으로 설정
bellmanFord(N, M, edges, start);
return 0;
}
5. 코드 설명
위의 코드는 벨만-포드 알고리즘을 C++로 구현한 것입니다. 각 부분을 상세히 설명하겠습니다.
- Edge 구조체: 도로 정보를 담기 위한 구조체로, 출발점 u, 도착점 v, 가중치 weight를 포함합니다.
- bellmanFord 함수: 최단 거리 계산을 수행하는 함수입니다. 종합적으로 최단 거리를 측정하고, 음의 사이클을 체크하여 결과를 출력합니다.
- 초기 거리 설정: 최단 거리를 무한대로 초기화하고, 출발점(start)의 거리는 0으로 설정합니다.
- V-1 회 반복: 각 도로(간선)를 검사하여 거리 업데이트를 수행합니다.
- 음의 사이클 체크: V번째 반복에 대해 거리 변화를 확인하여, 음의 사이클 존재 여부를 판단합니다.
6. 복잡도 분석
벨만-포드 알고리즘의 시간 복잡도는 O(V * E)입니다. 여기서 V는 정점의 수, E는 간선의 수를 뜻합니다. 이는 모든 간선을 V-1 번 순회하면서 거리 갱신을 수행하기 때문입니다. 적은 숫자의 간선과 정점의 경우에는 좋은 성능을 보이지만, 모든 정점과 간선의 개수가 많아질 경우 성능 저하가 발생할 수 있습니다.
7. 연습 문제
다음 연습 문제를 통해 벨만-포드 알고리즘을 더욱 깊이 이해할 수 있습니다:
- 문제: 특정 그래프에서 음의 사이클이 존재하는지를 판별하고, 그 사이클을 출력하시오.
- 문제: 여러 출발점으로부터 동시에 최단 거리를 계산하는 알고리즘을 구현하시오.
- 문제: 보다 복잡한 그래프 데이터 구조를 만들고, 관련 알고리즘을 벨만-포드 알고리즘으로 확장하시오.
8. 결론
이번 강좌를 통해 벨만-포드 알고리즘의 기본 개념과 C++를 이용한 구현 방법을 살펴보았습니다. 코딩테스트에서 복잡한 그래프 문제를 해결하는 데 많은 도움이 되기를 바랍니다. 코드를 직접 구현하고, 다양한 경우를 테스트해보는 것은 알고리즘을 마스터하는 데 큰 도움이 될 것입니다.
코딩 연습을 지속적으로 하여 다양한 문제를 풀어보시기 바랍니다. 감사합니다!