백준 1916번
오늘 풀어본 문제는 백준의 1916번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$N$ 개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 $M$ 개의 버스가 있다. 우리는 $A$ 번째 도시에서 $B$ 번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. $A$ 번째 도시에서 $B$ 번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 $1$ 부터 $N$ 까지이다.
입력
첫째 줄에 도시의 개수 $N$ $(1 \leq N \leq 1,000)$ 이 주어지고 둘째 줄에는 버스의 개수 $M$ $(1 \leq M \leq 100,000)$ 이 주어진다. 그리고 셋째 줄부터 $M+2$ 줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 $0$ 보다 크거나 같고, $100,000$ 보다 작은 정수이다.
그리고 $M+3$ 째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
풀이과정
1번째 시도
이 문제를 처음 보고 다익스트라 알고리즘을 사용하여 최단 경로를 찾는 문제라는 것을 알 수 있었다. 버스로 이동하는 비용을 각 간선의 길이로 생각하여 그래프를 구성하면 쉽게 풀 수 있는 문제라고 생각했다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int N, M;
vector<int> shortest;
vector<pii> graph[1001];
struct cmp {
bool operator()(const pii& p1, const pii& p2) {
return p1.second > p2.second;
}
};
void dijkstra(int departure);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
shortest.resize(N + 1, INT_MAX);
cin >> M;
for (int i = 0; i < M; i++) {
int start, end, cost;
cin >> start >> end >> cost;
graph[start].emplace_back(make_pair(end, cost));
}
int departure, destination;
cin >> departure >> destination;
dijkstra(departure);
cout << shortest[destination];
return 0;
}
void dijkstra(int departure) {
priority_queue<pii, vector<pii>, cmp> pq;
shortest[departure] = 0;
pq.push(make_pair(departure, 0));
while (!pq.empty()) {
pii currentNode = pq.top();
pq.pop();
for (auto& nextNode : graph[currentNode.first]) {
if (shortest[nextNode.first] > shortest[currentNode.first] + nextNode.second) {
shortest[nextNode.first] = currentNode.second + nextNode.second;
pq.push(make_pair(nextNode.first, shortest[nextNode.first]));
}
}
}
}
실행 결과 ‘시간 초과’ 가 발생하였다.
2번째 시도
분명 다익스트라 알고리즘을 제대로 구현했다고 생각했는데 시간 초과가 나와서 당황했다. 비슷한 상황을 겪은 사람이 있을까 해서 질문 게시판을 확인해보았고, 무엇이 문제인지 알 수 있었다.
우선순위 큐에서 이미 더 짧은 길이의 경로로 업데이트된 정점이 더 비효율적인 경로의 길이를 가지고 다른 노드의 거리를 업데이트 하는 절차를 거치는 것이 문제였다. 길이가 당연히 더 길기 때문에 진짜로 업데이트가 이루어지는 것은 아니지만, 비교하는 작업을 거치는 과정 자체가 불필요하게 수행되었던 것이다.
코드는 다음과 같이 수정하였다.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int N, M;
vector<int> shortest;
vector<pii> graph[1001];
struct cmp {
bool operator()(const pii& p1, const pii& p2) {
return p1.second > p2.second;
}
};
void dijkstra(int departure);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
shortest.resize(N + 1, INT_MAX);
cin >> M;
for (int i = 0; i < M; i++) {
int start, end, cost;
cin >> start >> end >> cost;
graph[start].emplace_back(make_pair(end, cost));
}
int departure, destination;
cin >> departure >> destination;
dijkstra(departure);
cout << shortest[destination];
return 0;
}
void dijkstra(int departure) {
priority_queue<pii, vector<pii>, cmp> pq;
shortest[departure] = 0;
pq.push(make_pair(departure, 0));
while (!pq.empty()) {
pii currentNode = pq.top();
pq.pop();
if (currentNode.second > shortest[currentNode.first]) continue;
for (auto& nextNode : graph[currentNode.first]) {
if (shortest[nextNode.first] > shortest[currentNode.first] + nextNode.second) {
shortest[nextNode.first] = currentNode.second + nextNode.second;
pq.push(make_pair(nextNode.first, shortest[nextNode.first]));
}
}
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
처음에 문제를 보고 간단한 다익스트라 알고리즘 문제라고 좋아했는데, 뒤통수를 맞아버렸다. ‘틀렸습니다’가 나올 수는 있겠다고 생각했지만 ‘시간 초과’는 전혀 예상하지 못했다. 당황스럽긴 했어도 앞으로 다익스트라 알고리즘을 쓸 때 어떻게 최적화를 할 수 있는지를 배울 수 있었던 꽤 유익했던 문제였다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1916