1. 문제
https://www.acmicpc.net/problem/1865
2. 적용할 알고리즘
처음에는 단순히 BFS로 하다가
결국에는 알고리즘 분류를 보고 "벨만포드"를 처음으로 알게 되었다.
벨만포드 알고리즘은 그래프에서 간선의 값이 음수일 때 사용하여
한 노드에서 다른 노드까지의 최소 거리를 알아낼 수 있다.
다익스트라 알고리즘과 비슷하나 그리디한 접근 방식을 사용하지 않고
각각의 반복마다 모든 간선을 확인하여 O(VE)가 되서 다익스트라에 비해
시간이 더 오래 걸린다.
하지만 간선의 값이 음수일 때 사용할 수 있다는게 장점이다.
3. 풀이
이 문제에서 원하는 것은 한 노드에서 출발하여 같은
노드로 시간이 0보다 적게 걸려 도착할 수 있냐는 것이다.
이 말은 그 노드에서 출발하여 되돌아올 수 있는 음수 사이클이 존재하여
그 사이클이 돌 때마다 시간을 줄일 수 있냐는 말이 된다.
위 그림처럼 음수 사이클이 만들어지게 된다면
노드 1에서 다른 노드까지 걸리는 시간은 값이 -4인 간선 때문에
계속해서 작아져 음수가 될 것이고
그 노드까지 걸리는 시간이 음수가 된다면
원래 위치로 돌아 왔을 때 시간이 되돌아간 경우가 된다.
따라서, "음수 사이클이 존재한다면 시간이 되돌아간 경우가 있다"
음수 사이클 존재의 확인을 벨만포드 알고리즘을 통해 알 수 있다.
노드의 개수가 n일 때, n - 1번 동안
각 간선을 거쳐 해당 노드로 가는 비용을 계산하여
최단 거리 테이블을 갱신하고 난 후 한 번 더 계산을 수행한다.
만약 갱신이 또 일어난다면 그것은 음수 사이클이 존재한다는 의미이다.
아무 갱신이 일어나지 않고 최단 거리 테이블이 완성됐다면 음수 사이클이 없다는 의미이다.
4. 코드
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<tuple>
using namespace std;
typedef long long ll;
const int INF = 1000'0000;
vector<pair<int, int>> adj[505];
int n, m, w;
int d[505];
bool bf()
{
fill(d, d + 505, INF);
d[1] = 0;
//n - 1번 동안 모든 간선을 확인해가며 최소 비용을 계산한다.
for (int i = 0; i < n - 1; i++)
{
for (int j = 1; j <= n; j++)
{
for (auto nxt : adj[j])
{
d[nxt.first] = min(d[nxt.first], d[j] + nxt.second);
}
}
}
//음수 사이클이 존재하는지 확인한다.
for (int j = 1; j <= n; j++)
{
for (auto nxt : adj[j])
{
if (d[j] + nxt.second < d[nxt.first]) return true;
}
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n >> m >> w;
for (int i = 1; i <= n; i++) adj[i].clear();
for (int i = 0; i < m; i++)
{
int s, e, t;
cin >> s >> e >> t;
adj[s].push_back({ e, t });
adj[e].push_back({ s, t });
}
for (int i = 0; i < w; i++)
{
int s, e, t;
cin >> s >> e >> t;
adj[s].push_back({ e, -t });
}
cout << (bf() ? "YES" : "NO") << '\n';
}
}
5. 느낀 점
그래프 문제에서 다익스트라, 벨만포드, 플로이드 알고리즘은
가끔 나오긴 하지만 유용하게 쓰일 때가 있으니 이에 대한
배경지식을 잘 쌓아놓도록 하자...