[C++] 백준/BOJ - 1865 : 웜홀

문제 이해 단계

https://www.acmicpc.net/problem/1865

1865번: 웜홀

N개의 지점과 그 지점 사이에는 M개의 도로와 W개의 웜홀이 존재한다.
여기서 도로는 양방향이고 웜홀은 단방향이다.

도로와 웜홀의 정보는 공통적으로
(시작 지점, 도착 지점, 가는 시간)으로 들어온다.

웜홀은 시작했을 때보다 도착했을 때 시간이 거꾸로 가게 된다.

한 지점에서 출발하여 다시 출발했던 지점을 돌아올 때,
출발했을 때보다 시간이 돌아가있는 것이 가능한가?를 묻는 문제

 

---

문제 접근 단계

가능한 지점의 수(N)는 최대 500개까지이고
도로의 수(M)는 최대 2,500개, 웜홀의 수(W)는 최대 200개이다.

모든 지점을 한 번씩만 탐색하는 것이라면
시간초과를 신경 쓰지 않아도 되겠지만,
한번 방문했던 지점을 다시 방문하지 말라는 말이 없다.

즉, 여러 번 방문이 가능해서 시간초과에 대해서 계속 신경 써야 한다.

---

웜홀의 정점과 간선 연결

일단 그래프 탐색 문제임에는 확실하기 때문에,
입력으로 주어진 방향 정보에 따라서 그래프를 연결해 준다.

그런데 한 가지 문제가 되는 것은
웜홀을 어떻게 연결할 것인가?이다.

웜홀을 통해 이동했을 때는 시작했을 때보다
도착했을 때 시간이 거꾸로 간다고 했다.

그러니까 그냥 이동했을 때, 걸린 시간만큼 빼주면 되는 것이다.
이를 다른 말로 하면 (-걸린 시간)만큼 더해준다고도 할 수 있다.

이를 토대로 예시 그림을 그려보자.
해당 그림은 예제 입력 1의 2번 케이스를 그린 그림이다.

예제 입력1의 테스트케이스2

이제 한 지점에서 출발했을 때의 시간보다,
도착했을 때 작아지는 시간을 찾으며 된다.

사실 그렇게 되려면 당연히 음수가 포함될 수밖에 없으니 웜홀이 포함돼야 한다.

1번에서 출발했을 때를 생각해 보자.
1 -> 3 -> 1으로 간다고 생각하면 4 - 8 = -4이다.

출발했을 때 0이었는데 -4로 돌아왔다.
정답이 된다.

여기서 멈추지 말고 계속해보자.
-4 -> -8 -> - 12 -> - 16 ->...

이렇게 음의 무한대로 가게 된다.

음의 무한대?? 그렇다.

이 문제는 결국에 벨만-포드 알고리즘을 이용해
음의 사이클이 발생하는지를 구하는 문제였던 것이다.

---

변형된 벨만-포드 알고리즘

벨만-포드 알고리즘은 한 지점에서 다른 노드까지 가는 최단 거리를 구하는 알고리즘이다.

다익스트라 알고리즘과 다른 점은 가중치에 음수가 포함되어 있어도 구할 수가 있다는 점이다.

핵심적인 점은
만약 음의 사이클(음의 무한대로 반복)되는 것이 있으면 이를 감지할 수 있다.

하지만 벨만-포드 알고리즘은 시작 지점을 1로 보고
지점 1의 최단거리를 0으로 잡고 시작한다.

하지만 이 문제는 모든 지점에서 출발할 수 있다.
또한 모든 그래프가 연결되어 있다는 말도 없다.

그래프가 끊어져 있는 경우

위와 같은 경우는 일반적인 벨만-포드 알고리즘을 적용해서
지점 1에서 시작하면 음의 사이클이 발생하지 않는 것으로 출력될 것이다.

하지만 보다시피 지점 3과 지점 4에서 음의 사이클이 발생된다.

그렇기 때문에 일반적인 벨만-포드 알고리즘으로는 구할 수 없으니 변형이 필요하다. 
어떤 식으로 변형해야 할까?

if(dist [i] == INF) continue; 부분을 삭제해 주는 것이다.

해당 부분을 삭제해 줌으로써, 모든 노드에 대해 검사가 가능하게 하는 것이다.
이렇게 하면 전체 노드에 대한 음의 사이클 검사가 가능해진다.

위와 같은 방식으로 검사를 할 수 있다.
이제 변형된 벨만 포드를 사용하여 문제를 풀어보자.

 

---

문제 구현 단계

#define INF 999999

vector<pair<pair<int,int>,int>> v;
bool success = false; // 음의 싸이클 발생 유무 판단

// 매개변수 -> 노드의 개수
void bellman_ford(int N){
    if(success) return; // 음의 싸이클이 발생했다면 더이상 할 필요 없음
    int dist[501]; // 각 노드의 최소 거리를 담는 배열
    fill(dist,dist+501,INF); // INF로 초기화

    // N-1번 반복
    for(int i = 1; i < N; i++){
        // 모든 간선을 훑음
        for(int j = 0; j < v.size(); j++){
            int from = v[j].first.first;
            int to = v[j].first.second;
            int time = v[j].second;
            // 최솟값 갱신
            if(dist[to] > dist[from]+time){
                dist[to] = dist[from]+time;
            }
        }
    }
    // N번째 최솟값 갱신(한번 더 해줌)
    for(int j = 0; j < v.size(); j++){
        int from = v[j].first.first;
        int to = v[j].first.second;
        int time = v[j].second;
        // 여기서 갱신이 일어나면 음의 싸이클이 발생하는 것
        if(dist[to] > dist[from]+time){
            success = true; // 음의 싸이클 발생
            return;
        }
    }
}

벨만포드를 변형한 함수이다.
매개변수로 노드의 개수를 받는다.

각 노드의 최소거리를 기억해 두기 위해, 배열을 선언하여 INF로 초기화해 둔다.
이는 최솟값을 담기 위해 최대한 큰 값을 저장해 두는 것이다.

벨만포드 자체는 간단하다.

전체 간선을 검사하여 모든 노드의 최소 거리를 갱신해 준다.
여기서 보면 continue가 없는 것을 확인할 수 있다.

이를 N-1번 반복하고, 마지막으로 한번 더 해준다.

만약 마지막으로 해줄 때 갱신이 일어난다면 음의 사이클이 발생한 것이다.
음의 사이클이 발생했다면, success = true로 바꾸고 끝낸다.

핵심적인 설명은 여기까지이다.
이제 아래에 나머지 코드를 올리고 끝내겠다.

#include <iostream>
#include <vector>
#include <utility>
#include <string>

#define INF 999999
using namespace std;



vector<pair<pair<int,int>,int>> v;
bool success = false; // 음의 싸이클 발생 유무 판단

// 매개변수 -> 노드의 개수
void bellman_ford(int N){
    if(success) return; // 음의 싸이클이 발생했다면 더이상 할 필요 없음
    int dist[501]; // 각 노드의 최소 거리를 담는 배열
    fill(dist,dist+501,INF); // INF로 초기화

    // N-1번 반복
    for(int i = 1; i < N; i++){
        // 모든 간선을 훑음
        for(int j = 0; j < v.size(); j++){
            int from = v[j].first.first;
            int to = v[j].first.second;
            int time = v[j].second;
            // 최솟값 갱신
            if(dist[to] > dist[from]+time){
                dist[to] = dist[from]+time;
            }
        }
    }
    // N번째 최솟값 갱신(한번 더 해줌)
    for(int j = 0; j < v.size(); j++){
        int from = v[j].first.first;
        int to = v[j].first.second;
        int time = v[j].second;
        // 여기서 갱신이 일어나면 음의 싸이클이 발생하는 것
        if(dist[to] > dist[from]+time){
            success = true; // 음의 싸이클 발생
            return;
        }
    }
}
int main(){
    int TC;
    scanf("%d",&TC);
    while(TC--){
        v.clear();
        success = false;
        int N,M,W;
        scanf("%d %d %d",&N,&M,&W);
        v.reserve(M+W+1);

        for(int i = 0; i < M; i++){
            int v1,v2,v3;
            cin >> v1 >> v2 >> v3;
            v.push_back({make_pair(v1,v2),v3});
            v.push_back({make_pair(v2,v1),v3});
        }
        for(int i = 0; i < W; i++){
            int v1,v2,v3;
            cin >> v1 >> v2 >> v3;
            v.push_back({make_pair(v1,v2),-v3});
        }
        bellman_ford(N);
        if(success) printf("YES\n");
        else printf("NO\n");
    }
}

 

---

시행착오

벨만포드 알고리즘 어렵다..

처음에 어렴풋이 이 생각이 났었는데,
구현하는 법을 까먹기도 했고 설마 해서 다른 방식을 구현했다.

근데 변형까지 거치니까 너무 어려웠다.
이해하는데 꽤 걸렸다.

벨만 포드 알고리즘을 두 번째 풀어보는데 또 틀리니까 좀.. ㅎㅎ

열심히 하자..

https://toss.me/howudong

howudong님에게 보내주세요