코딩 테스트에 자주 등장하는 알고리즘 중 하나가 바로 벨만-포드 알고리즘입니다. 이 글에서는 벨만-포드 알고리즘의 개념, 작동 방법, 그리고 실제 문제에 적용하는 방법을 단계별로 설명하겠습니다. 코딩 테스트와 취업 준비에 유용한 정보를 제공하기 위해 다양한 예제와 함께 상세한 풀이 과정을 포함시켰습니다.
벨만-포드 알고리즘 소개
벨만-포드 알고리즘은 가중치가 있는 그래프에서 단일 출발점(source)에서 다른 모든 정점까지의 최단 경로를 찾는 데 사용됩니다. 이 알고리즘은 음의 가중치가 있는 간선을 허용하지만, 음의 사이클이 포함된 경우에는 최단 경로를 제공할 수 없습니다. 따라서 알고리즘을 적용하기 전 그래프에 음의 사이클이 존재하는지 여부를 확인해야 합니다.
벨만-포드 알고리즘의 특징
- 정점 수가 V일 때, 시간 복잡도는 O(VE)입니다.
- 다리 데이터의 포맷이 다양할 수 있습니다.
- 최단 경로는 음의 가중치가 없는 그래프에서도 효과적으로 탐색이 가능합니다.
- 음의 사이클 검출 기능이 내장되어 있습니다.
문제: 최단 경로 찾기
다음은 벨만-포드 알고리즘을 이용하여 최단 경로를 찾는 문제입니다.
문제 설명
가중치가 있는 방향 그래프가 주어질 때, 특정 출발점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하세요. 그래프는 음의 가중치를 포함할 수 있습니다. 만약 음의 사이클이 존재하면, ‘Negative Cycle’이라는 메시지를 출력해야 합니다.
입력 형식
첫 번째 줄에는 정점의 수 V (1 ≤ V ≤ 1000)와 간선의 수 E (1 ≤ E ≤ 10,000)가 주어진다. 두 번째 줄에는 출발 정점 S (1 ≤ S ≤ V)가 주어진다. 이후 E줄에 걸쳐 각 간선에 대한 정보가 u, v, w (1 ≤ u, v ≤ V, -10^5 ≤ w ≤ 10^5)의 형태로 주어진다.
출력 형식
각 정점까지의 최단 경로 길이를, 공백으로 구분하여 출력한다. 음의 사이클이 존재하면 'Negative Cycle'를 출력한다.
문제 풀이
1. 문제 이해 및 분석
문제를 해결하기 위해 먼저 입력으로 주어지는 그래프 정보를 파악해야 합니다. 정점과 간선의 개수, 출발 정점을 이해해야 최단 경로를 구하는 과정으로 나아갈 수 있습니다. 이 문제는 벨만-포드 알고리즘의 기본적인 구조를 잘 활용해야 합니다.
2. 알고리즘 설계
벨만-포드 알고리즘은 다음의 단계로 진행됩니다:
- 모든 간선을 기반으로 최단 경로 값을 초기화합니다. 출발점은 0, 다른 모든 정점은 무한대(infinity)로 설정합니다.
- 정점의 수 – 1 만큼의 횟수 동안 모든 간선을 검사하고, 최단 경로를 갱신합니다.
- 모든 간선을 다시 검사하여, 최단 경로를 갱신할 수 있다면 음의 사이클이 존재하는 것으로 판단합니다.
3. 자바 코드 구현
이제 위에서 설명한 알고리즘을 바탕으로 자바 코드를 작성해 보겠습니다.
import java.util.*;
public class BellmanFord {
static class Edge {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int V = sc.nextInt(); // 정점의 수
int E = sc.nextInt(); // 간선의 수
int S = sc.nextInt(); // 출발 정점
List edges = new ArrayList<>();
for (int i = 0; i < E; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
int weight = sc.nextInt();
edges.add(new Edge(u, v, weight));
}
int[] dist = new int[V + 1];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[S] = 0;
// 알고리즘 실행
for (int i = 1; i <= V - 1; i++) {
for (Edge edge : edges) {
if (dist[edge.u] != Integer.MAX_VALUE &&
dist[edge.u] + edge.weight < dist[edge.v]) {
dist[edge.v] = dist[edge.u] + edge.weight;
}
}
}
// 음의 사이클 검출
for (Edge edge : edges) {
if (dist[edge.u] != Integer.MAX_VALUE &&
dist[edge.u] + edge.weight < dist[edge.v]) {
System.out.println("Negative Cycle");
return;
}
}
// 최단 경로 출력
for (int i = 1; i <= V; i++) {
if (dist[i] == Integer.MAX_VALUE) {
System.out.print("Infinity ");
} else {
System.out.print(dist[i] + " ");
}
}
}
}
4. 코드 설명
위 코드는 벨만-포드 알고리즘의 전체 흐름을 담고 있습니다:
- 우선 edge 리스트를 사용하여 모든 간선 데이터를 저장합니다.
- 거리 배열(dist)을 선언하고 출발점의 거리를 0으로 초기화합니다.
- 안쪽 loop에서 각 간선을 반복하며, 최단 거리를 갱신합니다.
- 모든 간선에 대해서 다시 검토한 후, 음의 사이클 여부를 확인합니다.
5. 테스트 및 검증
코드를 완성한 후, 다양한 테스트 케이스를 통해 알고리즘의 올바른 작동 여부를 확인해야 합니다. 예를 들어:
입력: 5 8 1 1 2 4 1 3 3 2 3 1 3 2 -1 2 4 2 3 4 5 4 5 -3 5 4 2 출력: 0 3 3 5 Infinity
6. 결론
벨만-포드 알고리즘은 최단 경로 문제를 해결하기 위해 매우 유용한 도구입니다. 음의 가중치를 허용하는 특성 덕분에 다양한 그래프 문제에 적용할 수 있습니다. 이 알고리즘의 이해와 구현은 코딩 인터뷰 및 알고리즘 시험에서 높은 점수를 얻기 위한 필수 능력 중 하나입니다.
마무리
벨만-포드 알고리즘에 대한 이번 강좌가 도움이 되셨다면 좋겠습니다. 코딩 테스트 준비에 실질적인 기여를 할 수 있기를 바랍니다. 알고리즘을 다양한 문제에 적용해 보며 심화 학습을 이어가세요!