문제 소개
당신은 A 지점에서 B 지점까지 가는 가장 빠른 버스 노선을 찾는 프로그램을 작성해야 합니다. 여러 개의 버스 노선이 있고 각각의 노선은 정해진 정류소를 지나며, 정류소 간의 이동 시간은 모두 다르게 설정되어 있습니다. 최종 목표는 특정한 A 지점에서 B 지점까지의 가장 빠른 경로를 찾고, 해당 경로의 소요시간을 반환하는 것입니다.
문제 설명
주어진 노선은 다음과 같이 표현됩니다. 각 노선은 정류소 간의 이동 시간을 가지며, 정류소는 다음과 같은 형태로 표현됩니다:
[ {busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]}, {busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]}, {busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]}, {busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]}, ]
입력
첫 번째 매개변수로는 버스 노선의 배열, 두 번째 매개변수로는 A 지점과 B 지점이 주어집니다.
출력
가장 빠른 경로의 소요 시간을 출력합니다. 경로가 없다면 -1을 출력합니다.
예제
입력: const routes = [ {busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]}, {busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]}, {busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]}, {busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]}, ]; const start = "A"; const end = "B"; 출력: 5
해결 방법
이 문제를 해결하기 위해 우리는 그래프 탐색 알고리즘을 사용할 수 있습니다. 정류소는 노드로, 정류소 간 시간은 그 노드들 간의 엣지의 가중치로 표현할 수 있습니다. 적절한 알고리즘으로는 BFS(너비 우선 탐색)나 Dijkstra 알고리즘이 있습니다. 이 문제에서는 Dijkstra 알고리즘이 더 효과적입니다, 왜냐하면 모든 간선의 가중치가 다를 수 있어서 가장 짧은 경로를 찾기 위해 최적화된 방법이 필요하기 때문입니다.
Dijkstra 알고리즘 개요
Dijkstra는 가중치가 있는 그래프에서 최단 경로를 찾기 위한 알고리즘으로, 현재 노드에서 인접 노드로 이동할 때의 비용을 계속 업데이트하면서 최종 목표 노드로 가는 경로를 탐색합니다. 이를 위해 우리는 각 정류소와 비용을 기록할 수 있는 우선순위 큐를 사용합니다.
코드 구현
function getFastestBusRoute(routes, start, end) { // Priority queue for processing the stops const pq = new MinPriorityQueue(); const distances = {}; const parents = {}; // Initialize distances and priority queue for (const route of routes) { for (const stop of route.stops) { distances[stop.stop] = Infinity; parents[stop.stop] = null; } } // Starting point distances[start] = 0; pq.enqueue(start, 0); while (!pq.isEmpty()) { const currentStop = pq.dequeue().element; // If we reach the target stop, return the distance if (currentStop === end) { return distances[currentStop]; } for (const route of routes) { for (let i = 0; i < route.stops.length - 1; i++) { const stop1 = route.stops[i].stop; const stop2 = route.stops[i + 1].stop; const time = route.stops[i + 1].time - route.stops[i].time; if (stop1 === currentStop) { const newTime = distances[stop1] + time; if (newTime < distances[stop2]) { distances[stop2] = newTime; parents[stop2] = stop1; pq.enqueue(stop2, newTime); } } } } } return -1; // If there's no path to the end } // Example usage const routes = [ {busRoute: "1", stops: [{stop: "A", time: 0}, {stop: "B", time: 5}, {stop: "C", time: 10}]}, {busRoute: "2", stops: [{stop: "A", time: 0}, {stop: "D", time: 3}, {stop: "B", time: 8}]}, {busRoute: "3", stops: [{stop: "B", time: 0}, {stop: "C", time: 4}, {stop: "E", time: 6}]}, {busRoute: "4", stops: [{stop: "D", time: 0}, {stop: "E", time: 2}, {stop: "B", time: 7}]}, ]; const start = "A"; const end = "B"; console.log(getFastestBusRoute(routes, start, end)); // Output: 5
결론
이번 강좌에서는 주어진 버스 노선 정보를 바탕으로 가장 빠른 경로를 찾는 알고리즘 문제를 해결하는 방법을 배웠습니다. Dijkstra 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾아주는 매우 유용한 방법입니다. 각 단계에서 실제로 어떻게 탐색을 진행하는지 이해하고, 이를 코딩으로 구현하는 과정에서 많은 도움이 되었기를 바랍니다.
추가 연습 문제
이번 문제를 통해 Dijkstra 알고리즘을 익혔다면, 다음과 같은 변형 문제들도 시도해 보세요:
- 특정 노선만을 사용하여 경로를 찾아야 하는 문제
- 정류소 간의 이동 시간이 아닌 이동 거리로 경로를 찾는 문제
- 최소 경로가 아닌 최다 경로를 찾는 문제