문제
때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.
시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.
입출력
1 Test Case
2 지점의 수, 도로의 개수, 웜홀의 개수 (N , M, W)
3 ~ M 도로 시작점, 도착점, 걸리는 시간 (S, E, T)
4 ~ W 웜홀 시작점, 도착점, 걸리는 시간 (S, E, T)
//입력
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
//출력
NO
YES
C++
복사
풀이
가중치가 음수가 나오는 그래프이므로 벨만-포드 알고리즘을 사용한다.
특정 지점에서 출발하여 자기 자신으로 돌아올 수 있고, 그 때의 시간값이 0보다 작다(음수) 이므로
음수 사이클이 생기는지의 판단을 통해 정답을 구할 수 있다.
모든 지점에서의 벨만-포드를 계산하는것이 직관적인 생각이지만, 전체 그래프 내에서 싸이클이 생기는지만 판단하더라도 다른 정점을 구할 필요가 없다.
대신 오리지널 벨만-포드는 거리를 구하기 위해서 dist 값이 갱신되지 않은 경우에는 pass 했지만
단절된 그래프에서도 싸이클 유무를 판단해야 하기 때문에 dist[j] != INF 구문을 삭제한다.
if (dist[next_node] > next_weight + dist[j]) { // (dist[j] != INF && dist[next_node] > next_weight + dist[j])
if (k == N - 1) flag = 1;
dist[next_node] = next_weight + dist[j];
}
C++
복사
•
벨만-포드 함수
void bellman() {
int flag = 0;
dist[1] = 0;
for (int k = 0; k < N; k++) { //(V - 1)번의 루프
for (int j = 1; j <= N; j++) {
for (auto data : graph[j]) {
int next_node = data.first;
int next_weight = data.second;
if (dist[next_node] > next_weight + dist[j]) {
if (k == N - 1) flag = 1;
dist[next_node] = next_weight + dist[j];
}
}
}
}
if (flag) cout << "YES\n";
else cout << "NO\n";
}
C++
복사
•
Main 함수 동작
int main() {
fastio;
int T;
int a, b, c;
cin >> T;
while (T--) {
cin >> N >> M >> W;
init();
for (int i = 0; i < M; i++) {
cin >> a >> b >> c;
graph[a].push_back({ b,c });
graph[b].push_back({ a,c });
}
for (int i = 0; i < W; i++) {
cin >> a >> b >> c;
graph[a].push_back({ b,-c });
}
bellman();
}
return 0;
}
C++
복사
중요
기본적으로 벨만-포드 알고리즘은 최단 거리를 구하기 위해서 사용된다. 따라서 초기에 모든 거리를 INF로 초기화하고, 검사 구문에서 아래와 같이 dist[j] ≠ INF 를 통해 단절된 곳에 대한 거리값 갱신을 막아준다.
if ((dist[j] != INF && dist[next_node] > next_weight + dist[j])) {
if (k == N - 1) flag = 1;
dist[next_node] = next_weight + dist[j];
}
C++
복사
하지만 단순하게 전체 그래프에서의 싸이클 발생 여부에 대해 검사하는 경우에는 모든 노드를 고려해주어야 하므로, dist[j] ≠ INF 조건을 없애주어야 한다.
