[BOJ] 9874 : Wormholes

문제 링크

9874번: Wormholes (acmicpc.net)

9874번: Wormholes

평면상 모든 구멍들의 페어를 조합하는 백트래킹 문제.

문제 해석

일단 영어로 된 문제라 문제 해석이 어려웠다. 간락하게 설명하자면 Farmer John의 농장에는 N개의 구멍이 있다. 이 구멍들은 각각 연결되어있으며 총 N/2개의 쌍이 생긴다. 구멍마다 일대일 대응으로 쌍이 연결된다는 뜻이다. 구멍 A와 B가연결되어 있다고 한다면 A로 들어가면 B로 나온다. 반대로 B로 들어가면 A로 나오게 된다.

그렇게 되면 위와 같은 상황이 발생할 수도 있다. A와 B 사이 임의의 지점에서 출발한다면 B로 들어가서 A로 나오게 되고 다시 가다보면 또 B로 들어가서 A로 나오는 무한루프를 돌게될 수도 있다. 이때 Bessie는 항상 +X 방향으로만 움직인다. 이러한 루프가 하나라도 존재하는 구멍들의 페어를 정하는 방법의 수를 출력해보자.

풀이

N이 최대 12이므로 그렇기 크지않다. 백트래킹을 이용해서 페어를 정하는 모든 경우의 수를 다 탐색해준다. 이때 페어의 개수는 항상 N/2개 이므로 페어가 N/2개 만들어졌을 때 무한루프가 하나라도 존재하는지 체크한다.

void backtracking(int idx, vector<pair<int, int>> pairs, bool visited[]) {
	if (pairs.size() == N / 2) {
		//루프 존재하는지 탐색
		for (int i = 0; i < N; i++) {
			if (is_loop(i, pairs)) {
				ans++;
				break;
			}
		}
		return;
	}
	for (int i = idx; i < N-1; i++) {
		if (visited[i] == false) {
			for (int j = i + 1; j < N; j++) {
				if (visited[j] == false) {
					visited[i] = true;
					visited[j] = true;
					pairs.push_back({ i,j });
					backtracking(i + 1, pairs, visited);
					pairs.pop_back();
					visited[i] = false;
					visited[j] = false;
				}
			}
		}
	}
}

 이미 페어가 정해진 구멍인지 체크하기 위해서 visited라는 배열을 만들어주었다.

페어의 수가 N/2개가 되었다면 모든 구멍을 출발점으로 아래 함수를 통해 루프가 존재하는지 탐색해준다.

bool is_loop(int st, vector<pair<int,int>> pairs) {
	bool visited[MAX_N];
	memset(visited, false, sizeof(visited));
	int now = st;
	for (int i = 0; i < N; i++) {
		if (visited[now]) //이미 들어갔던 구멍이면 루프가 존재
			return true;
		visited[now] = true; //아니라면 방문 체크
		for (int j = 0; j < pairs.size(); j++) { //반대편 구멍을 찾아줌
			if (pairs[j].first == now) {
				now = pairs[j].second;
				break;
			}
			else if (pairs[j].second == now) {
				now = pairs[j].first;
				break;
			}
		}
		bool chk = false;
		for (int j = 0; j < wormholes.size(); j++) {
			if (wormholes[now].first < wormholes[j].first && wormholes[now].second == wormholes[j].second) {
				now = j;
				chk = true;
				break;
			}
		}
		if (!chk)
			return false;
	}
	return false;
}

Bessie는 항상 +X방향으로 움직이므로 현재 위치의 좌표보다보다 x 값이 크고, y값은 같은 구멍에 들어가게 된다.

만약 루프가 존재하면 true 아니라면 false를 반환한다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 12 + 5;
vector<pair<int, int>> wormholes;
int N;
int ans;
 
bool is_loop(int st, vector<pair<int,int>> pairs) {
    bool visited[MAX_N];
    memset(visited, false, sizeof(visited));
    int now = st;
    for (int i = 0; i < N; i++) {
        if (visited[now]) //이미 들어갔던 구멍이면 루프가 존재
            return true;
        visited[now] = true; //아니라면 방문 체크
        for (int j = 0; j < pairs.size(); j++) { //반대편 구멍을 찾아줌
            if (pairs[j].first == now) {
                now = pairs[j].second;
                break;
            }
            else if (pairs[j].second == now) {
                now = pairs[j].first;
                break;
            }
        }
        bool chk = false;
        for (int j = 0; j < wormholes.size(); j++) {
            if (wormholes[now].first < wormholes[j].first && wormholes[now].second == wormholes[j].second) {
                now = j;
                chk = true;
                break;
            }
        }
        if (!chk)
            return false;
    }
    return false;
}
 
void backtracking(int idx, vector<pair<int, int>> pairs, bool visited[]) {
    if (pairs.size() == N / 2) {
        //루프 존재하는지 탐색
        for (int i = 0; i < N; i++) {
            if (is_loop(i, pairs)) {
                ans++;
                break;
            }
        }
        return;
    }
    for (int i = idx; i < N-1; i++) {
        if (visited[i] == false) {
            for (int j = i + 1; j < N; j++) {
                if (visited[j] == false) {
                    visited[i] = true;
                    visited[j] = true;
                    pairs.push_back({ i,j });
                    backtracking(i + 1, pairs, visited);
                    pairs.pop_back();
                    visited[i] = false;
                    visited[j] = false;
                }
            }
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        wormholes.push_back({ x,y });
    }
    sort(wormholes.begin(), wormholes.end());
    vector<pair<int, int>> temp;
    bool visited[MAX_N];
    memset(visited, false, sizeof(visited));
    backtracking(0, temp, visited);
    cout << ans << "\n";
    return 0;
}