문제 설명
한 도시에서 여러 개의 버스 노선이 운영되고 있으며, 각 노선은 정해진 정류소를 순회합니다.
당신은 A 정류소에서 B 정류소까지 가는 가장 빠른 경로를 찾아야 합니다.
버스는 정해진 시간에 출발하며, 각 정류소에서 정차하는 시간과 이동 시간을 고려해야 합니다.
아래와 같은 데이터가 주어졌을 때, 가장 빠른 버스 노선을 찾는 알고리즘을 작성하시오.
입력 형식
- 첫 번째 줄에는 정류소의 수 N(1 ≤ N ≤ 1000)과 버스 노선의 수 M(1 ≤ M ≤ 10000)이 주어진다.
- 두 번째 줄부터 M개의 줄에는 각 버스 노선에 대한 정보가 다음 형식으로 주어진다:
시작 정류소, 도착 정류소, 소요 시간 - 마지막 줄에는 A 정류소와 B 정류소의 번호가 주어진다.
출력 형식
첫 번째 줄에 A 정류소에서 B 정류소까지 가는 가장 짧은 시간(분)을 출력한다.
만약 도착할 수 없으면 -1을 출력한다.
예제 입력
5 7
1 2 10
1 3 20
2 3 5
2 4 10
3 4 10
4 5 15
1 5
예제 출력
25
문제 풀이 과정
이 문제를 해결하기 위해 우리는 최단 경로 알고리즘을 사용해야 합니다.
주어진 그래프는 가중치가 있는 방향 그래프이므로, 다익스트라 알고리즘을 적합하게 사용할 수 있습니다.
다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 방법으로,
주로 비가중치 그래프에 적합합니다. 하지만 가중치가 있을 경우에도 효과적으로 적용할 수 있습니다.
다익스트라 알고리즘의 기본 원리
다익스트라 알고리즘은 다음과 같은 기본 원리로 작동합니다:
- 출발 정점을 설정하여 최단 경로를 0으로 초기화하고, 나머지 정점은 무한대로 초기화합니다.
- 처리되지 않은 정점 중에서 최단 경로가 가장 짧은 정점을 선택합니다.
- 선택된 정점에 인접한 정점들의 경로를 갱신합니다.
- 이 과정을 모든 정점이 처리될 때까지 반복합니다.
C++ 코드 구현
다음은 위의 알고리즘을 바탕으로 한 C++ 코드 구현입니다.
#include
#include
#include
#include
using namespace std;
const int INF = numeric_limits::max();
void dijkstra(int start, int n, vector>> &graph, vector &dist) {
priority_queue, vector>, greater>> pq;
dist[start] = 0;
pq.push({0, start});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto &neighbor : graph[u]) {
int v = neighbor.first;
int weight = neighbor.second;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
}
int main() {
int N, M;
cin >> N >> M;
vector>> graph(N + 1); // N 정류소
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
}
int A, B;
cin >> A >> B;
vector dist(N + 1, INF);
dijkstra(A, N, graph, dist);
if (dist[B] == INF) {
cout << -1 << endl;
} else {
cout << dist[B] << endl;
}
return 0;
}
코드 설명
위의 코드는 다익스트라 알고리즘을 사용하여 주어진 정류소에서 최단 경로를 찾는 방법을 구현하고 있습니다.
주요 단계는 다음과 같습니다:
- 주어진 입력을 바탕으로 그래프를 인접 리스트 형태로 저장합니다.
- 시작 정류소에서부터 다른 정류소까지의 최단 경로를 구하기 위해 다익스트라 함수를 호출합니다.
- 결과적으로 도착 정류소까지의 최단 경로가 무한대이면 도달할 수 없다는 의미로 -1을 출력하고,
그렇지 않으면 최단 경로의 경과 시간을 출력합니다.
결론
이번 강좌에서는 여러 개의 버스 노선과 정류소를 가진 그래프에서 시작점과 도착점 사이의 최단 경로를
찾는 문제를 다뤄보았습니다. 다익스트라 알고리즘을 통해 최단 경로를 구하는 개념과 그 구현 방법을
학습했습니다. 이를 바탕으로 다른 유사한 문제들도 해결할 수 있는 기초를 다졌습니다.