백준1865(웜홀)

jh Seo·2024년 1월 6일
백준벨만포드 알고리즘한번에 못 푼 문제
0

백준

목록 보기
170/180
post-thumbnail

개요

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

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

접근 방식

  1. 일반 벨만포드 문제처럼 접근했고, 싸이클 여부만 체크했는데 계속 틀렷다.
    이유는 시작점이 명시되어있지 않아서이다!!
    어떤 지점이든 출발점으로 삼고 진행할 수 있다.

  2. 따라서 모든 지점에서 벨만포드를 진행하기보단
    각 도시마다 BFS를 돌아서 컴퍼넌트를 찾은 후, 해당 컴퍼넌트 내에서 벨만포드를 각자 진행하기로 했다.

       //도시 컴퍼넌트마다 벨만포드 돌려야하므로 모든 도시에 대해서 반복
   for (int i = 0; i < N; i++)
   {
       //visited[i]가 true이면 방문한 도시이다. 이미 조사한 컴퍼넌트에 속한 도시이므로 continue
       if (visited[i]) continue;

       //현재 컴퍼넌트의 원소들 받아올 set 초기화
       componentElem.clear();

       int startNode = i;
       //시작 도시 방문배열이랑 dist 0으로 초기화
       visited[startNode]=true;
       dist[startNode]=0;
       //BFS함수를 통해 현재 컴퍼넌트의 원소들 set에 insert한 후, 순회한 원소들 visited true로 체크함
       int comSize=BFS(startNode);

       // 싸이클 여부 확인용 변수
       bool minusCycle = false;

       // cycle 체킹용으로 N번 루프
       for (int i = 0; i < comSize; i++)
       {
           //컴퍼넌트의 노드 거쳤을 때의 최단경로 갱신
           for (auto iter=componentElem.begin();iter!=componentElem.end();++iter)
           {
               //각 원소와 연결된 도시들에 대해 벨만포드 진행
               for (auto &elem : adj[*iter])
               {
                   int nextNode = elem.first, nextDist = elem.second;
                   if (dist[*iter]!=INF && dist[nextNode] > dist[*iter] + nextDist)
                   {
                       dist[nextNode] = dist[*iter] + nextDist;
                       if (i == comSize-1)
                           minusCycle = true;
                   }
               }
           }
       }

    도시 갯수만큼 반복문을 돈다.

    각 도시마다 방문여부를 체크한다. (방문을 했다는 뜻은 미리 조사한 컴퍼넌트 내부의 도시라는 뜻이다.)
    방문 안한 도시라면 시작 도시로 잡고,
    시작도시에서 BFS를 돌아 컴퍼넌트 내부의 도시들을 set에 insert해준다.

    컴퍼넌트 내부 도시들이set에 저장된 상태이므로 해당 도시들 대상으로 벨만 포드를 진행해주면 된다.

  3. 문제점이 하나 있다!
    여기서 3일정도를 막혀서 고생했는 데, 바로 간선은 양방향이지만 웜홀이 단방향이라는 것이다!!ㅜㅜ

    무슨 뜻이냐면 컴퍼넌트 A, B가 있다고 하자.
    A 에서 B로 가는 웜홀은 없지만 B에서 A로 가는 웜홀이 있다고 하자.

    컴퍼넌트 A를 먼저 BFS를 통해 조사한다고 해보자.
    A의 세 도시가 set에 insert된다.
    하지만 A에서 B로 가는 간선이 없다.
    따라서 A 내부를 순회하는 BFS함수를 통해 B에서 A를 향한 웜홀은 체크할 수 없다.

    이제 컴퍼넌트 B를 BFS를 통해 조사하는 과정에서, B에서 A로 향한 웜홀이 존재하므로
    해당 웜홀을 BFS가 탐색한다.

    하지만 A의 도시는 이미 방문한 도시이므로 visited배열이 true이다. 그냥 무시해버린다.

    여기서 문제가 발생했다!!!!

    처음에 짰던 코드는 벨만포드에서 컴퍼넌트 내부 도시 갯수만큼만 반복을 한다.
    B컴퍼넌트에서 벨만포드를 진행해보자.
    2번째((도시갯수-1)) 루프에서 웜홀이 연결된 도시의 비용이 변경되었다고 하자.
    3번째 루프에서 B에서 A로 연결된 웜홀을 통해 A컴퍼넌트 도시의 비용을 변경하게 된다.

    문제는 N번째에서 변화가 발생하면 싸이클 처리를 해버리는 벨만포드 알고리즘 특성이다.
    B컴퍼넌트를 처리하던중 3번째 루프에서 변화가 발생했으므로 싸이클 처리를 해버린다.
    B가 아닌 A컴퍼넌트 도시의 비용 변경인데도 말이다!

    해결방법은 단순하다.
    루프 횟수를 1 늘리고 싸이클 체크하는 인덱스도 1 늘려준다.

     for (int i = 0; i < comSize+1; i++)
       {
           //컴퍼넌트의 노드 거쳤을 때의 최단경로 갱신
           for (auto iter=componentElem.begin();iter!=componentElem.end();++iter)
           {
               //각 원소와 연결된 도시들에 대해 벨만포드 진행
               for (auto &elem : adj[*iter])
               {
                   int nextNode = elem.first, nextDist = elem.second;
                   if (dist[*iter]!=INF && dist[nextNode] > dist[*iter] + nextDist)
                   {
                       dist[nextNode] = dist[*iter] + nextDist;
                       if (i == comSize)
                           minusCycle = true;
                   }

    이렇게 1 늘려주면 외부 컴퍼넌트의 도시 비용을 변경한 후에
    한번 더 체크하는 꼴이므로 변경되는 노드는 없다.

전체 코드

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>

using namespace std;
//도로 저장용 도시 i,j사이 거리 k일때, adj[i]={j,k}
vector<pair<int,int>> adj[501];
//도시 컴퍼넌트를 구성하는 도시 원소들
set<int> componentElem;
//최단거리 
long long dist[501];
//방문 배열
bool visited[501];
long long INF=1e18;
void Solution();

//각 반복마다 초기화
void Init(){
    for(int i=0;i<501;i++){
        adj[i].clear();
    }
    fill(dist,dist+501,INF);
    fill(visited,visited+501,false);   
}

//각 컴퍼넌트 순회해서 set에 구성요소 넣고 사이즈 반환 
int BFS(int sN){
    int size=0;
    queue<int> q;
    int cur=sN;
    q.push(cur);
    while(!q.empty()){
        size++;
        int cur = q.front();
        componentElem.insert(cur);
        q.pop();
        for (auto &elem : adj[cur])
        {
            int nextNode=elem.first;
            if (!visited[nextNode])
            {
                visited[nextNode] = true;
                q.push(nextNode);
            }
        }
    }
    return size;
}

//테스트케이스 수 입력받고 그만큼 실행
void Input(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++){
        Init();
        Solution();
    }

}

// 도시를 BFS함수를 통해 컴퍼넌트별로 나누고 모든 컴포넌트에 대해서 싸이클 체크
void Solution(){

    // 도시, 길, 웜홀 갯수
    int N, M, W;
    cin >> N >> M >> W;
    // 시작도시, 끝도시, 걸리는 시간/ 줄어드는 시간
    int S, E, T;
    for (int i = 0; i < M; i++)
    {
        cin >> S >> E >> T;
        // 양방향그래프
        adj[S - 1].push_back(make_pair(E - 1, T));
        adj[E - 1].push_back(make_pair(S - 1, T));
    }
    // 웜홀일 때, 감소하므로 -T
    for (int i = 0; i < W; i++)
    {
        cin >> S >> E >> T;
        adj[S - 1].push_back(make_pair(E - 1, -T));
    }

    //도시 컴퍼넌트마다 벨만포드 돌려야하므로 모든 도시에 대해서 반복
    for (int i = 0; i < N; i++)
    {
        //visited[i]가 true이면 방문한 도시이다. 이미 조사한 컴퍼넌트에 속한 도시이므로 continue
        if (visited[i]) continue;

        //현재 컴퍼넌트의 원소들 받아올 set 초기화
        componentElem.clear();

        int startNode = i;
        //시작 도시 방문배열이랑 dist 0으로 초기화
        visited[startNode]=true;
        dist[startNode]=0;
        //BFS함수를 통해 현재 컴퍼넌트의 원소들 set에 insert한 후, 순회한 원소들 visited true로 체크함
        int comSize=BFS(startNode);

        // 싸이클 여부 확인용 변수
        bool minusCycle = false;

        // cycle 체킹용으로 N번 루프
        for (int i = 0; i < comSize+1; i++)
        {
            //컴퍼넌트의 노드 거쳤을 때의 최단경로 갱신
            for (auto iter=componentElem.begin();iter!=componentElem.end();++iter)
            {
                //각 원소와 연결된 도시들에 대해 벨만포드 진행
                for (auto &elem : adj[*iter])
                {
                    int nextNode = elem.first, nextDist = elem.second;
                    if (dist[*iter]!=INF && dist[nextNode] > dist[*iter] + nextDist)
                    {
                        dist[nextNode] = dist[*iter] + nextDist;
                        if (i == comSize)
                            minusCycle = true;
                    }
                }
            }
        }
        //싸이클 생기면 YES 출력
        if (minusCycle)
        {
            cout << "YES\n";
            return;
        }
        if(dist[startNode]<0)
        {
            cout<<"YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main()
{
    Input();
}

다른 풀이

https://www.acmicpc.net/board/view/72995
위 게시물에서 jh05013 님이 정리해주신 부분을 보고 풀어본 풀이이다.
현재 문제에서는 싸이클이 발생하는 컴퍼넌트가 있는지 체크하는 문제이다.

위에 내가 푼 방식은 BFS를 통해 각 컴퍼넌트를 구한 후 해당 컴퍼넌트 내부에서 벨만포드를 적용하는 방식이다.

그런데 약간의 트릭을 쓰면 모든 정점에서 전부 체크할 수 있다.
N개의 도시가 있다고 하면 N+1번째 가상의 도시를 설정한 후, 해당 도시에서 모든 정점으로
단방향 경로를 잇는 것이다.

그 후, N+1번째 가상의 도시에서 벨만 포드 알고리즘을 시작하면 모든 컴퍼넌트의 싸이클 여부를 체크할 수 있다!!

다른 풀이 코드

#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>

using namespace std;
//도로 저장용 도시 i,j사이 거리 k일때, adj[i]={j,k}
vector<pair<int,int>> adj[501];
//최단거리 
long long dist[501];

long long INF=1e18;
void Solution();

//각 반복마다 초기화
void Init(){
    for(int i=0;i<501;i++){
        adj[i].clear();
    }
    fill(dist,dist+501,INF);
}

//테스트케이스 수 입력받고 그 만큼 실행
void Input(){
    int N;
    cin>>N;
    for(int i=0;i<N;i++){
        Init();
        Solution();
    }

}

void Solution(){

    // 도시, 길, 웜홀 갯수
    int N, M, W;
    cin >> N >> M >> W;
    // 시작도시, 끝도시, 걸리는 시간 / 줄어드는 시간
    int S, E, T;
    for (int i = 0; i < M; i++)
    {
        cin >> S >> E >> T;
        // 양방향그래프
        adj[S - 1].push_back(make_pair(E - 1, T));
        adj[E - 1].push_back(make_pair(S - 1, T));
    }
    // 웜홀일 때, 감소하므로 -T
    for (int i = 0; i < W; i++)
    {
        cin >> S >> E >> T;
        adj[S - 1].push_back(make_pair(E - 1, -T));
    }

    //가상의 N번째 도시를 생성 후, 모든 도시에 단방향 간선을 이음(비용은 0이든 1이든 상관없음)
    for(int i=0;i<N;i++){
        adj[N].push_back(make_pair(i,1));
    }
    
    //N번째 도시부터 시작
    dist[N]=0;
    bool isCycle=false;
    //벨만포드 적용
    for(int  i=0; i<N+1;i++){
        for(int j=0;j<N+1;j++){
            for(auto& elem : adj[j]){
                int nextNode=elem.first,nextDist=elem.second;
                if(dist[j]!=INF&& dist[nextNode] > dist[j]+nextDist){
                    dist[nextNode]=dist[j]+nextDist;
                    if(i==N) isCycle=true;
                }
            }
        }
    }
    if(isCycle) cout<<"YES\n";
    else cout << "NO\n";
}

int main()
{
    Input();
}

문풀후생

오래 고민한 만큼 문제점이 많이 와닿았다.
컴퍼넌트 별로 나눠도 단방향인 간선이 있다면 한번 더 생각해볼 좋은 문제이다.

또한 새로운 점을 생성후, 모든 점과 잇는 방식을 통해 간단하게 모든 컴퍼넌트의 싸이클 유무 여부를 조사하는 방법읋 새로 배웠는데 굉장히 스파크가 튀는 참신한 방식인것 같다.
좋은 걸 배워간다..

레퍼런스

https://www.acmicpc.net/board/view/72995

profile
jh Seo
코딩 창고!
이전 포스트

백준1738(골목길)

다음 포스트

백준 2839(설탕 배달)

0개의 댓글