https://www.acmicpc.net/problem/1916
문제
> N개의 도시가 있다.
> 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.
> 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.
> A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라.
> 도시의 번호는 1부터 N까지이다.
> 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다.
> 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다.
> 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다.
> 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다.
> 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
> 그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.
> 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.접근
다익스트라를 사용하여 도시까지의 최소비용을 구한다. 우선순위 큐로 주어진 비용 0, 주어진시작점으로 큐에 넣고 시작하여 다음 가능한 경로를 가져온다. 가능한 경로 까지의 비용을 계산해 큐에 다 넣고 우선순위 큐로 비용이 낮은 도시부터 뽑아온다. 해당 도시에서 또 갈 수 있는 도시를 따지는데 가는 비용과 기존에 저장된 최소비용을 비교해 기존이 더 작다면 스킵, 새로운게 더 작다면 큐에넣고 갱신을 해준다. 이 과정을 반복하며 각 도시까지의 최소 비용을 구한다.
문제해결
> N과 M을 입력받고 각 도시까지의 최소비용을 저장할 rst벡터에 최악의 비용을 초기값으로 저장해둔다.
> 도시의 버스 노선을 저장할 bus 벡터를 만들고 입력받아 저장한다.
> 시작도시, 도착도시를 A,B로 입력받고 최소비용을 구하는메소드 Root를 호출한다.
> 메소드에서 우선순위 큐를 선언해주고 첫 시작점과 시작비용을 큐에넣는다. 시작점을 비용 0으로 초기화 해준다.
> while문에서 큐의 젤 앞에 있는 애를 가져오면서 rst에 저장된 어떤 도시까지의 비용과 현재 큐에 있는 비용을 비교해서 큐에서 가져온 비용이 더 크다면 볼 필요 없으므로 스킵한다.
(우선순위 큐로 인해 후순위로 밀려있는 예전에 들어온 값이 앞에서 갱신이 이미 다돼서 더 작은 값을 가지고있을때, 이로 인해 for문의 불필요한 연산을 하지않기 위해서이다.)
> for문에서 해당 도시에서 갈 수 있는 도시를 탐색한다. 비용을 계산하는데 기존에 저장된 비용보다 작은 경로들만 큐에 넣고 비용을 갱신한다.
> 모든 경로가 탐색이 끝나면 각각의 도시까지의 최소비용이 들어있으므로 목적도시에 저장된값을 반환해주고 이를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int N, M;
int A, B;
int rst[1001];
vector<vector<pair<int, int>>> bus;
int Root(int start, int end)
{
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, start });
rst[start] = 0;
while (!pq.empty())
{
int fweight = pq.top().first;
int fnode = pq.top().second;
pq.pop();
if (rst[fnode] < fweight) continue;
for (auto a : bus[fnode])
{
int nweight = a.first + fweight;
if (rst[a.second] > nweight)
{
pq.push({ nweight, a.second });
rst[a.second] = nweight;
}
}
}
return rst[end];
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
cin >> M;
for (int i = 1; i <= N; i++) rst[i] = INT_MAX;
bus.resize(N+1, vector<pair<int, int>>());
for (int i = 0; i < M; i++)
{
int a, b, c;
cin >> a >> b >> c;
bus[a].push_back({ c, b });
}
cin >> A >> B;
cout << Root(A, B) << '\n';
}
후기
Root메소드의 내부 동작(다익스트라 알고리즘)을 이해하고 왜 필요한지를 이해할 수 있는 문제였다. 메모리 초과와 시간초과가 계속 나서 뭘 고쳐야, 줄여야 될지를 계속 동작흐름을 따라갈 수 있는 경험이었다.
