[Algorithm] 백준 9874 - Wormholes

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

9874번: Wormholes

대강 해석

존이 물리 실험을 하던중 N (2 <= N <= 12, N은 짝수) 개의 웜홀이 농장에 생겼습니다.

웜홀은 한 쌍으로 연결할 수 있으며 A와 B로 연결 되어있다고 하면 A로 들어가면 B로 나오고 B로 들어가면 A로 나오게 됩니다.

존의 소 베시는 +x방향으로 밖에 이동하지 못합니다.

베시가 운이 없게도 어떠한 장소에 있을때 루프에 같히게 되도록 웜홀이 연결 되었을때 루프가 생기는 경우를 찾아주세요.

 

과정

1. 웜홀을 한 쌍씩 전부 연결한다.
2. 연결된 웜홀들을 체크하여 무한루프가 생겼는지 확인한다.

 

주의할 점

웜홀의 좌표가 x순으로 정렬되어 있는지 혹은 웜홀에서 나왔을 때 어떤 웜홀로 가는지 x좌표가 최소값인지 확인하자.

정렬되어 있지 않은 경우 단순히 처음부터 시작하여 현재좌표보다 다른 웜홀의 좌표가 큰 경우를 찾는다면 찾은 웜홀의 x좌표가 최소임을 보장할 수 없다.

예제

4
0 0
1 0
1 1
0 1

정답 : 2

6
879221060 76350727
161945371 76350727
380619073 76350727
896289713 76350727
852891025 852349940
519959866 76350727

정답 : 10

 

코드

#include<iostream>

#include<vector>

#include<algorithm>

 

using namespace std;

 

int N;

vector<pair<int,int> > W;

int chk[15];

int ret=0;

 

void Initialize(){

    fill(&chk[0],&chk[15],-1);

}

 

void Input(){

    int a,b;

    cin>>N;

 

    for(int i=0;i<N;i++){

        cin>>a>>b;

        W.push_back({a,b});

    }

    sort(W.begin(),W.end());

}

 

int next_hole(int idx){

    int y = W[idx].second;

    int x = W[idx].first;

    for(int i=0;i<N;i++){

        int ny = W[i].second;

        int nx = W[i].first;

        if(y==ny && x<nx){

            return i;

        }

    }

    return -1;

}

 

bool calc(int now){

    bool loop[15];

    fill(&loop[0],&loop[15],false);

       

    int next;

    while(true){

        if(loop[now]) break;

       

        loop[now] = true;

        next = chk[now];

        now = next_hole(next);

        if(now==-1) return false;

    }

 

    return true;

}

 

void dfs(int idx, int cnt){

    if(cnt==N){

        for(int i=0;i<N;i++){

            if(calc(i)){

                ret++;

                break;

            }

        }

        return ;

    }

 

    for(int i=idx;i<N;i++){

        if(chk[i]!=-1) continue;

       

        for(int j=i+1;j<N;j++){

            if(chk[j]!=-1) continue;

            chk[i]=j;

            chk[j]=i;

 

            dfs(i+1,cnt+2);

 

            chk[i]=chk[j]=-1;

        }

    }

}

 

void Solution(){

    dfs(0,0);

 

    cout<<ret<<'\n';

}

 

int main(){

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

 

    Input();

    Initialize();

    Solution();

 

    return 0;

}