백준 1238번
오늘 풀어본 문제는 백준의 1238번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
$N$개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 $N$명의 학생이 $X$ $(1 \leq X \leq N)$ 번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 $M$개의 단방향 도로들이 있고 $i$번째 길을 지나는데 $T_i$ $(1 \leq T_i \leq 100)$ 의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
입력
첫째 줄에 $N$ $(1 \leq N \leq 1,000)$, $M$ $(1 \leq M \leq 10,000)$, $X$가 공백으로 구분되어 입력된다. 두 번째 줄부터 $M+1$번째 줄까지 $i$번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 $T_i$가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 $A$에서 다른 도시 $B$로 가는 도로의 개수는 최대 $1$개이다.
모든 학생들은 집에서 $X$에 갈수 있고, $X$에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
출력
첫 번째 줄에 $N$명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
풀이과정
첫 번째 시도
이 문제는 최단 경로를 찾는 것이 목표이기 때문에 다익스트라 알고리즘을 사용해야 한다. 다익스트라 알고리즘이 무엇인가 하면, 시작점에서 주변 노드들의 거리를 업데이트하고, 시작점에서의 거리가 가장가까운 점에서 또 주변 노드들의 거리를 업데이트 하는 방식으로 진행되는 알고리즘이다. 자세한 내용 설명은 생략하도록 하겠다.
이 문제가 특이한 점은, 파티하러 가는 최단 경로도 알아야 하고, 파티하고 돌아가는 최단 경로도 알아야 한다는 점이다. 이 문제 상황에서 보면 도로가 단방향이기 때문에 둘이 서로 다를 수 있다. 그렇기 때문에 다익스트라 알고리즘을 두 번 써야 한다.
모든 집에서 파티하는 집으로 가는 경로의 최솟값 알아내기 위해서는, 그래프의 선분 방향을 거꾸로 저장하여, 파티하는 집에서 모든 집까지 가는 경로의 최솟값을 알아내는 문제로 바꿔버린 후 다익스트라 알고리즘을 사용하여 알아낼 수 있고, 파티하는 집에서 모든 집으로 되돌아가는 경로의 최솟값을 알아내는 것은 그냥 그래프 그대로 저장해서 바로 다익스트라 알고리즘으로 알아내면 된다. 그래서 두 번 써야 하는 것이다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
struct cmp {
bool operator()(pair<int, int> p1, pair<int, int> p2) {
return p1.second > p2.second;
}
};
int numberOfStudents;
int shortestDistanceToParty[1001] = { 0, };
int shortestDistanceToBye[1001] = { 0, };
vector<pair<int, int>> graphToParty[1001];
vector<pair<int, int>> graphToBye[1001];
void dijkstra(int departure, bool goToParty);
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int numberOfRoads, destination;
cin >> numberOfStudents >> numberOfRoads >> destination;
for (int i = 1; i <= numberOfStudents; i++) {
if (i != destination) {
shortestDistanceToParty[i] = INT_MAX;
shortestDistanceToBye[i] = INT_MAX;
}
}
for (int i = 0; i < numberOfRoads; i++) {
int nodeA, nodeB, tempTime;
cin >> nodeA >> nodeB >> tempTime;
graphToParty[nodeB].emplace_back(make_pair(nodeA, tempTime));
graphToBye[nodeA].emplace_back(make_pair(nodeB, tempTime));
}
dijkstra(destination, true);
dijkstra(destination, false);
priority_queue<int> pq;
for (int i = 1; i <= numberOfStudents; i++) {
pq.push(shortestDistanceToParty[i] + shortestDistanceToBye[i]);
}
cout << pq.top();
return 0;
}
void dijkstra(int departure, bool goToParty) {
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
bool checked[1001] = { 0, };
pq.push(make_pair(departure, 0));
while (!pq.empty()) {
pair<int, int> currentNode = pq.top();
pq.pop();
if (checked[currentNode.first] == true) {
continue;
}
checked[currentNode.first] = true;
if (goToParty) {
for (auto i : graphToParty[currentNode.first]) {
if (shortestDistanceToParty[i.first] > currentNode.second + i.second) {
shortestDistanceToParty[i.first] = currentNode.second + i.second;
pq.push(make_pair(i.first, shortestDistanceToParty[i.first]));
}
}
}
else {
for (auto i : graphToBye[currentNode.first]) {
if (shortestDistanceToBye[i.first] > currentNode.second + i.second) {
shortestDistanceToBye[i.first] = currentNode.second + i.second;
pq.push(make_pair(i.first, shortestDistanceToBye[i.first]));
}
}
}
}
}
그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
CLASS 4 언저리의 문제들은 데이터구조 시간에 배웠던 내용들이 많이 보이는 것 같다. 당시에 저장해뒀던 강의노트들을 보면서 문제를 풀다보니, 학교 알고리즘 수업의 선수과목으로 데이터구조가 있는 이유를 알 것 같다.
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1238