안녕하세요! 이번 강좌에서는 취업을 위한 자바스크립트 코딩테스트 문제 중 하나인 ‘최단 경로 구하기’에 대해 다뤄보겠습니다. 이 문제는 알고리즘과 자료구조의 기본 원리를 이해하고 활용하는 데 큰 도움이 될 것입니다. 코딩 인터뷰에서 자주 등장하는 주제로, 우선순위 큐와 그래프 이론에 대한 이해가 필수입니다.
문제 설명
우리는 여러 도시와 도로의 관계를 그래프로 표현할 수 있다고 가정합니다. 각 도시는 노드(node)로 표현되고, 도로는 노드 간의 엣지(edge)로 표현됩니다. 우리는 한 도시에서 출발해 다른 도시까지의 최단 경로를 찾아야 합니다.
문제 정의
도시의 수 n, 도로의 수 m이 주어질 때, 특정 도시 k에서 출발해 모든 다른 도시까지의 최단 경로를 구하시오. 도로의 정보는 u와 v를 연결하는 가중치 w로 주어집니다. 가중치는 도로의 길이를 의미합니다.
입력 형식
n, m, k
u1, v1, w1
u2, v2, w2
...
um, vm, wm
출력 형식
최단 경로의 길이 배열
예를 들어, 다음과 같은 입력이 주어졌다고 가정합시다:
5 6 1
1 2 2
1 3 3
2 3 1
2 4 2
3 4 4
4 5 1
위의 예시에서 도시 1에서 시작하여 다른 도시들에 도달하는 최단 경로의 길이는 다음과 같습니다:
0
2
3
4
5
도시 1에서 출발하므로 최단 경로의 길이는 그 자신인 0을 포함하여 1에서 다른 도시로 가는 최단 거리입니다.
해결 방안
이 문제를 해결하기 위해서는 다익스트라 알고리즘을 사용할 수 있습니다. 다익스트라 알고리즘은 그래프에서 특정 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾기 위한 알고리즘으로, 우선순위 큐를 활용합니다.
다익스트라 알고리즘 설명
1) 초기화: 시작 도시의 거리는 0으로 설정하고, 나머지 도시는 무한대로 설정합니다.
2) 방문한 도시 저장: 방문한 도시는 따로 저장하여 중복 계산을 방지합니다.
3) 우선순위 큐 사용: 가장 짧은 거리를 가진 도시를 선택하여 진행합니다. 그 도시와 인접한 도시들의 거리를 업데이트합니다.
4) 반복: 모든 도시가 방문될 때까지 위의 과정을 반복합니다.
자바스크립트 구현 예제
이제 위의 알고리즘을 자바스크립트로 구현해보겠습니다.
function dijkstra(n, edges, start) {
const INF = Infinity;
const graph = Array.from({ length: n + 1 }, () => []);
const dist = Array(n + 1).fill(INF);
dist[start] = 0;
const pq = new MinPriorityQueue();
edges.forEach(([u, v, w]) => {
graph[u].push([v, w]);
graph[v].push([u, w]); // 무향 그래프의 경우
});
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
const { element: current, priority: currentDist } = pq.dequeue();
if (currentDist > dist[current]) continue; // 이미 최단 거리로 방문한 경우
for (const [neighbor, weight] of graph[current]) {
const newDist = currentDist + weight;
if (newDist < dist[neighbor]) {
dist[neighbor] = newDist;
pq.enqueue(neighbor, newDist);
}
}
}
return dist.slice(1); // 첫 번째 인덱스는 0이므로 제외
}
class MinPriorityQueue {
constructor() {
this.items = [];
}
enqueue(element, priority) {
this.items.push({ element, priority });
this.items.sort((a, b) => a.priority - b.priority);
}
dequeue() {
return this.items.shift(); // 가장 우선순위가 낮은 것을 반환
}
isEmpty() {
return this.items.length === 0;
}
}
// 사용 예시
const n = 5;
const edges = [
[1, 2, 2],
[1, 3, 3],
[2, 3, 1],
[2, 4, 2],
[3, 4, 4],
[4, 5, 1]
];
const start = 1;
console.log(dijkstra(n, edges, start)); // [0, 2, 3, 4, 5]
문제 풀이 과정 정리
1) 노드와 엣지의 개수를 초기화합니다.
2) 각 도시 간의 도로(엘지)를 그래프로 표현합니다.
3) 다익스트라 알고리즘을 통해 최단 경로를 계산합니다.
4) 최단 경로의 결과를 출력합니다.
결론
이번 강좌에서는 ‘최단 경로 구하기’ 문제를 통해 자바스크립트에서 그래프 알고리즘을 구현하는 방법을 배웠습니다. 다익스트라 알고리즘은 구현이 간단하면서도 다양한 문제에 적용할 수 있어 유용합니다. 실제 코딩테스트뿐만 아니라 알고리즘 경진대회에서도 종종 출제되므로 꼭 익혀두시길 바랍니다.
추가적으로 알고리즘을 보다 깊이 이해하기 위해 최단 경로 알고리즘의 다양한 변형(벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등)을 학습하는 것도 좋습니다. 이러한 알고리즘들의 차이점과 사용 사례를 이해함으로써 더 넓은 시야를 가질 수 있을 것입니다.
많은 도움이 되길 바라며, 다음 강좌에서 더 흥미로운 주제로 만나뵙겠습니다. 감사합니다!