백준 1865번
오늘 풀어본 문제는 백준의 1865번 문제1이다. 문제 풀이에 사용한 언어는 C++ 이다.
solved.ac 기준 CLASS
문제 정보
이 문제의 내용과 조건은 다음과 같다.
문제
때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 $N$개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.
시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 테스트케이스의 개수 $TC$ $(1 \leq TC \leq 5)$ 가 주어진다. 그리고 두 번째 줄부터 $TC$ 개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 $N$ $(1 \leq N \leq 500)$, 도로의 개수 $M$ $(1 \leq M \leq 2500)$, 웜홀의 개수 $W$ $(1 \leq W \leq 200)$ 이 주어진다. 그리고 두 번째 줄부터 $M+1$ 번째 줄에 도로의 정보가 주어지는데 각 도로의 정보는 $S$, $E$, $T$ 세 정수로 주어진다. $S$ 와 $E$ 는 연결된 지점의 번호, $T$는 이 도로를 통해 이동하는데 걸리는 시간을 의미한다. 그리고 $M+2$ 번째 줄부터 $M+W+1$ 번째 줄까지 웜홀의 정보가 $S$, $E$, $T$ 세 정수로 주어지는데 $S$ 는 시작 지점, $E$는 도착 지점, $T$ 는 줄어드는 시간을 의미한다. $T$ 는 $10,000$ 보다 작거나 같은 자연수 또는 $0$이다.
두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. 지점의 번호는 $1$ 부터 $N$ 까지 자연수로 중복 없이 매겨져 있다.
출력
$TC$ 개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력한다.
풀이과정
0번째 시도
사실 이걸 시도로 쳐야할지 애매하긴 하지만, 엄연히 제출 기록에 남아있는 시도이기 때문에 간단하게 언급만하고 넘어가겠다.
내가 PS를 할 때는 단순히 한 문제만 풀어서 올리고 마는게 아니고, 여러 가지 문제를 푼 다음에 특히 어려웠거나 인상깊었던 문제들에 대하여 올리는 편이다. 오늘도 마찬가지였지만, 다른 날에는 한 적이 없던 어처구니 없는 실수를 했다.
전혀 다른 문제의 코드를 이 문제의 제출에 넣어버린 것이다! 말할 것도 없이 '틀렸습니다' 가 떴고, 그 와중에 원래 문제에서도 틀렸다. (...) 어쨌든 0번째 시도에 대한 이야기는 여기까지만 하겠다. 꼭 필요한 내용은 아니지만 제출 기록을 열심히 찾아보는 사람이 있을까 하여 접은 상태로 남겨두겠다.
1번째 시도
이 문제는 벨만-포드 알고리즘을 사용해야하는 문제이다. 벨만-포드 알고리즘은 여러 가지 그래프 최단거리 경로 탐색 알고리즘 중 하나인데, 그래프에 음수 간선이 존재할 때 주로 쓰이며, 음수 간선으로 이루어진 ‘사이클’ 이 존재하는 지도 알고리즘에서 알아낼 수 있다.
이 문제는 딱히 어떤 최단거리를 구하라기 보다도, 시작 위치에 돌아왔을 때 시간을 되돌린 상태로 도착할 수 있는지 확인하는 것이 목표이기 때문에 ‘사이클’의 존재 여부를 판단하는 것이 문제에서 중요한 점이 된다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> edges;
int shortestPath[501] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M, W;
cin >> N >> M >> W;
edges.clear();
for (int i = 0; i < M; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, T));
edges.emplace_back(make_tuple(E, S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, -T));
}
shortestPath[1] = 0;
for (int i = 2; i <= N; i++) {
shortestPath[i] = INT_MAX;
}
for (int i = 1; i <= N - 1; i++) {
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[start] == INT_MAX) {
continue;
}
else {
shortestPath[end] = min(shortestPath[end], shortestPath[start] + length);
}
}
}
bool negativeCycleExists = false;
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[start] == INT_MAX) {
continue;
}
else {
if (shortestPath[end] > shortestPath[start] + length) {
negativeCycleExists = true;
break;
}
}
}
if (negativeCycleExists) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
실행 결과, ‘틀렸습니다’ 가 나왔다.
2번째 시도
분명히 알고리즘을 맞게 적용한 것 같은데, 뭐가 문제인지 이해할 수 없었다. 우선 $N-1$ 번 반복하던걸 $N$ 번 반복하도록 바꿔보는 시도를 했고, 그대로 제출을 해보았다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> edges;
int shortestPath[501] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M, W;
cin >> N >> M >> W;
edges.clear();
for (int i = 0; i < M; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, T));
edges.emplace_back(make_tuple(E, S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, -T));
}
shortestPath[1] = 0;
for (int i = 2; i <= N; i++) {
shortestPath[i] = INT_MAX;
}
for (int i = 1; i <= N; i++) {
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[start] == INT_MAX) {
continue;
}
else {
shortestPath[end] = min(shortestPath[end], shortestPath[start] + length);
}
}
}
bool negativeCycleExists = false;
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[start] == INT_MAX) {
continue;
}
else {
if (shortestPath[end] > shortestPath[start] + length) {
negativeCycleExists = true;
break;
}
}
}
if (negativeCycleExists) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
실행 결과, ‘틀렸습니다’ 가 나왔다.
3번째 시도
이번에 시도해본 방법은 갱신과정에서 방문한 적이 없는 노드인지 검사하는 과정을 제외하였다. 어짜피 방문한 적이 없는 노드에 대한 갱신이 일어나더라도 이후에 다른 값으로 제대로 갱신될 것이라고 기대하였다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> edges;
int shortestPath[501] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M, W;
cin >> N >> M >> W;
edges.clear();
for (int i = 0; i < M; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, T));
edges.emplace_back(make_tuple(E, S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, -T));
}
shortestPath[1] = 0;
for (int i = 2; i <= N; i++) {
shortestPath[i] = INT_MAX;
}
for (int i = 1; i <= N - 1; i++) {
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
shortestPath[end] = min(shortestPath[end], shortestPath[start] + length);
}
}
bool negativeCycleExists = false;
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[start] == INT_MAX) {
continue;
}
else {
if (shortestPath[end] > shortestPath[start] + length) {
negativeCycleExists = true;
break;
}
}
}
if (negativeCycleExists) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
실행 결과, ‘틀렸습니다’ 가 나왔다.
4번째 시도
이쯤되니 지치기 시작했다. 대체 뭐가 문제인지 이해가 안되었기 때문에 일단 다시 한 번 반복문의 반복 횟수를 바꾸어서 제출해 보았다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> edges;
int shortestPath[501] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M, W;
cin >> N >> M >> W;
edges.clear();
for (int i = 0; i < M; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, T));
edges.emplace_back(make_tuple(E, S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, -T));
}
shortestPath[1] = 0;
for (int i = 2; i <= N; i++) {
shortestPath[i] = INT_MAX;
}
for (int i = 1; i <= N; i++) {
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
shortestPath[end] = min(shortestPath[end], shortestPath[start] + length);
}
}
bool negativeCycleExists = false;
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[start] == INT_MAX) {
continue;
}
else {
if (shortestPath[end] > shortestPath[start] + length) {
negativeCycleExists = true;
break;
}
}
}
if (negativeCycleExists) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
실행 결과, ‘틀렸습니다’ 가 나왔다.
5번째 시도
코드를 다시 읽어보니, 마지막에 사이클을 판별하는 과정에서 갱신과정에서 방문한 적이 없는 노드인지를 검사하고 있었다. 반복문 내부만 제외해주고, 마지막에 검사과정에서는 제외해주지 않았던 것이다. 반복문 횟수가 역시 문제가 아니었던 것 같아 원래대로 돌려두었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> edges;
int shortestPath[501] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M, W;
cin >> N >> M >> W;
edges.clear();
for (int i = 0; i < M; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, T));
edges.emplace_back(make_tuple(E, S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, -T));
}
shortestPath[1] = 0;
for (int i = 2; i <= N; i++) {
shortestPath[i] = INT_MAX;
}
for (int i = 1; i <= N - 1; i++) {
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
shortestPath[end] = min(shortestPath[end], shortestPath[start] + length);
}
}
bool negativeCycleExists = false;
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[end] > shortestPath[start] + length) {
negativeCycleExists = true;
break;
}
}
if (negativeCycleExists) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
실행 결과, ‘틀렸습니다’ 가 나왔다.
6번째 시도
결국 다시 질문게시판에 들어가 글들을 조금 둘러보았고, INT_MAX 를 사용한 것이 원인이라는 사실을 알게되었다. 적당히 크고 오버플로우가 나지 않는 수로 바꿔주었다.
코드는 다음과 같이 작성하였다.
#include <bits/stdc++.h>
using namespace std;
vector<tuple<int, int, int>> edges;
int shortestPath[501] = { 0, };
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, M, W;
cin >> N >> M >> W;
edges.clear();
for (int i = 0; i < M; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, T));
edges.emplace_back(make_tuple(E, S, T));
}
for (int i = 0; i < W; i++) {
int S, E, T;
cin >> S >> E >> T;
edges.emplace_back(make_tuple(S, E, -T));
}
shortestPath[1] = 0;
for (int i = 2; i <= N; i++) {
shortestPath[i] = 1000000;
}
for (int i = 1; i < N; i++) {
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
shortestPath[end] = min(shortestPath[end], shortestPath[start] + length);
}
}
bool negativeCycleExists = false;
for (auto edge : edges) {
int start = get<0>(edge);
int end = get<1>(edge);
int length = get<2>(edge);
if (shortestPath[end] > shortestPath[start] + length) {
negativeCycleExists = true;
break;
}
}
if (negativeCycleExists) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
return 0;
}
그러자 드디어! 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.
마무리
오늘 문제 풀이 과정은 무언가 이상했다. 문제의 원인을 오랫동안 진단하고 신중하게 코드를 제출하지 않고, 그때그때 될 것 같은 방법만 생각해서 성급하게 했던 것이다.
앞으로는 훨씬 어려운 문제들도 많이 나올 것이고, 더 억울한 일도 많이 당할 텐데, 이대로는 안되겠다는 생각이 들었다. 오늘의 고생을 교훈 삼아 다른 문제들을 풀 때는 더 침착하고 신중하게 풀어야겠다.
그건 그렇고 요즘 그래프가 너무 많이 나오는 것 같다. CLASS 3, 4 에서는 물론이고, 학교 동아리 세미나에서 조차 그래프가 계속 나온다. 앞으로 더 질리도록 보게될 것 같다. 살려줘 🥕🥕🥕🥕🥕
오늘의 PS는 여기까지!
1: https://www.acmicpc.net/problem/1865