안녕하세요. 오늘은 자바스크립트 코딩테스트를 준비하는 여러분을 위해 벨만-포드 알고리즘에 대해 자세히 알아보겠습니다. 벨만-포드 알고리즘은 그래프 이론에서 최단 경로를 찾기 위한 알고리즘 중 하나로, 특히 음의 가중치를 가진 간선이 있는 경우에도 적용할 수 있다는 장점이 있습니다. 이번 글에서는 벨만-포드 알고리즘의 개요, 원리, 문제 해결 과정 및 자바스크립트 구현 방법에 대해 다룰 것입니다.
1. 벨만-포드 알고리즘 개요
벨만-포드 알고리즘은 한 정점에서 다른 정점까지의 최단 경로를 찾기 위해 사용하는 그래프 알고리즘입니다. 이 알고리즘은 다음과 같은 특징을 가지고 있습니다:
- 음의 가중치를 가진 간선이 있어도 사용할 수 있습니다.
- 그래프에 사이클이 존재하지 않거나, 음의 사이클이 존재하지 않음을 확인할 수 있습니다.
2. 벨만-포드 알고리즘의 원리
벨만-포드 알고리즘은 다음과 같은 원리로 작동합니다:
- 시작 정점을 설정하고, 해당 정점의 거리 값을 0으로 초기화합니다. 다른 모든 정점의 거리 값은 무한대로 설정합니다.
- 모든 간선을 한 번씩 검사하여, 각 간선의 시작 정점에서 끝 정점으로 가는 최단 거리를 갱신합니다.
- 이 과정을 정점의 개수 – 1만큼 반복합니다. (그래프에서 최단 경로는 최대
V - 1번의 간선을 지나기 때문입니다.) - 마지막으로 모든 간선을 다시 검사하여 거리 값이 업데이트되는 경우가 있으면, 음의 사이클이 존재한다고 판단합니다.
3. 문제 설명
다음과 같은 문제를 해결해 보겠습니다:
문제:
n개의 도시와m개의 도로가 주어질 때, 각 도로는 출발 도시에서 도착 도시까지의 거리를 나타내는 가중치가 있습니다.
일반적으로, 출발 도시는 1번 도시이고, 도착 도시는 n번 도시입니다.
1번 도시에서 n번 도시까지의 최단 거리를 구하는 함수를 작성하세요. (음의 간선이 있을 수 있습니다.)
4. 문제 해결 과정
이 문제를 벨만-포드 알고리즘을 이용해 해결하는 과정을 상세히 설명하겠습니다:
4.1. 입력 데이터 구조 설계
문제를 해결하기 위한 입력 데이터를 정의해야 합니다. 우선, 도시의 개수와 도로의 개수, 각 도로 정보를 담는 구조를 설계해야 합니다. 아래와 같이 객체 배열을 사용하여 도로를 표현할 수 있습니다:
// 도시 개수와 도로 개수
const n = 5; // 도시의 개수
const m = 8; // 도로의 개수
// 도로 정보 (출발 도시, 도착 도시, 거리)
const roads = [
{ from: 1, to: 2, weight: 4 },
{ from: 1, to: 3, weight: 2 },
{ from: 2, to: 3, weight: 5 },
{ from: 2, to: 4, weight: 10 },
{ from: 3, to: 2, weight: 1 },
{ from: 3, to: 4, weight: 3 },
{ from: 4, to: 5, weight: 3 },
{ from: 2, to: 5, weight: 12 }
];
4.2. 초기화
다음으로, 거리 값을 초기화합니다. 1번 도시의 거리는 0으로, 나머지 도시는 무한대로 설정합니다:
const INF = Infinity; // 무한대 값
const distance = Array(n + 1).fill(INF); // 1부터 n까지의 거리 배열
distance[1] = 0; // 시작 도시의 거리 초기화
4.3. 벨만-포드 알고리즘 구현
이제 벨만-포드 알고리즘을 구현합니다. 간선을 n-1번 반복하여 거리 값을 갱신합니다:
for (let i = 1; i < n; i++) {
for (const road of roads) {
if (distance[road.from] + road.weight < distance[road.to]) {
distance[road.to] = distance[road.from] + road.weight;
}
}
}
4.4. 음의 사이클 체크
마지막으로, 모든 간선을 다시 검사하여 음의 사이클이 있는지 확인하는 과정을 구현합니다:
let hasNegativeCycle = false;
for (const road of roads) {
if (distance[road.from] + road.weight < distance[road.to]) {
hasNegativeCycle = true; // 음의 사이클 존재
break;
}
}
if (hasNegativeCycle) {
console.log("음의 사이클이 존재합니다.");
} else {
console.log("최단 거리:", distance[n]);
}
5. 전체 코드
위의 모든 과정을 종합하여 완전한 자바스크립트 코드를 만들어 보겠습니다:
function bellmanFord(n, roads) {
const INF = Infinity;
const distance = Array(n + 1).fill(INF);
distance[1] = 0;
// 벨만-포드 알고리즘
for (let i = 1; i < n; i++) {
for (const road of roads) {
if (distance[road.from] + road.weight < distance[road.to]) {
distance[road.to] = distance[road.from] + road.weight;
}
}
}
// 음의 사이클 체크
let hasNegativeCycle = false;
for (const road of roads) {
if (distance[road.from] + road.weight < distance[road.to]) {
hasNegativeCycle = true;
break;
}
}
if (hasNegativeCycle) {
console.log("음의 사이클이 존재합니다.");
} else {
console.log("최단 거리:", distance[n]);
}
}
// 사용 예시
const n = 5;
const roads = [
{ from: 1, to: 2, weight: 4 },
{ from: 1, to: 3, weight: 2 },
{ from: 2, to: 3, weight: 5 },
{ from: 2, to: 4, weight: 10 },
{ from: 3, to: 2, weight: 1 },
{ from: 3, to: 4, weight: 3 },
{ from: 4, to: 5, weight: 3 },
{ from: 2, to: 5, weight: 12 }
];
bellmanFord(n, roads);
6. 마무리
이번 글에서는 벨만-포드 알고리즘의 기본 개념과 원리, 문제를 해결하는 과정을 자세히 살펴보았습니다. 해당 알고리즘은 음의 가중치를 가진 간선이 있을 때 유용하며, 그래프 이론을 학습하는 데 중요한 알고리즘 중 하나입니다. 코딩테스트에서 자주 출제되는 주제니만큼, 반드시 숙지하시기 바랍니다.
앞으로도 다양한 알고리즘과 문제 풀이를 통해 실력을 쌓기를 바라며, 질문이 있으면 언제든지 댓글로 남겨주세요. 감사합니다!