[알고스팟] 종만북 소풍 : PICNIC

https://algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

 

모든 친구가 서로 친한 친구의 쌍을 이루는 조합의 개수를 찾는 문제입니다.

n이 10이므로 모든 경우를 완전 탐색을 통해 찾아 가면서 가능한 경우만 세어주면 됩니다.

예를 들어 n이 6인경우 친구관계가 모두 친하다고 가정한다면, (1,2),(3,4),(5,6) , (1,3),(2,4),(5,6) ... 등 이 있습니다.

그러나 (1,2)와 (2,1) 쌍은 같으며 (3,4),(1,2)와 (1,2),(3,4) 의 단순한 쌍의 순서만 바뀐경우도 같습니다.

우리는 완전 탐색의 진행 순서를 강제하여 이러한 경우를 제거할 수 있습니다.

1. 번호가 작은 친구의 쌍을 우선적으로 찾아라.

2. 쌍을 찾는 친구는 자신보다 큰 번호의 친구와 쌍을 이룬다.

1번 규칙의 경우 (3,4)(1,2)의 경우는 발생하지 않습니다. (이전에 (1,2),(3,4)의 경우로 이미 세어졌겟죠.)

2번 규칙의 경우 (2,1)의 경우가 발생하지 않습니다. 만약 둘이 쌍을 이뤘다면 (1,2) ... 를 포함한 경우에 이미 세어졌습니다.

저는 비트마스킹을 통해 해결했습니다

만약 처음으로 3번친구와 1번친구가 짝을 맺은 경우 001010 로 나타낼수 있습니다.

쌍을 맺은 상태를 의미하는 state 변수가 (1<<3) 이 1이고 (1 << 1) 이 1인것을 의미하는 겁니다.

즉, 쌍을 이룬 친구는 1의 비트가 켜져있고, 그렇지 않은 친구는 0의 비트로 상태가 나타나겠죠.

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int map[10][10];
int visit[10]; // i번 친구와 쌍을 이룬 사람
int n,m,ans = 0;
void dfs(int state) { // 현재 누가 짝을 맺었는지 상태 
	if (state == (1 << n) - 1) { // 모두 쌍을 이룸 111111
		ans += 1;
		return;
	}
	for (int i = 0; i < n; i++) {
		if (state & (1 << i)) { // 이미 i번친구는 쌍을 이뤘으므로
			continue;
		}
		// 쌍을 이루지 않은 가장 작은 친구부터 우선적으로 찾는다. [규칙 1번]
		for (int j = i + 1; j < n; j++) { // 나보다 큰 친구와 쌍을 이룬다. [규칙 2번]
			if (!map[i][j] || (state & (1 << j))) { // 서로 친구가 아니거나, j 번 친구가 쌍을 이룸
				continue;
			}
			dfs(state | (1 << i) | (1 << j));
		}
		break; // i번 친구를 쌍을 맺지 않고 다음으로 넘어가면 [규칙 1번]에 위배된다.
	}
	return;
}
void solve() {
	memset(visit, -1, sizeof(visit)); // 쌍을 이룬 상태인가?
	memset(map, 0, sizeof(map)); // 쌍을 이룬 상태인가?
	ans = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		map[a][b] = 1;
		map[b][a] = 1; // 서로 친구 관계이므로 양방향 표시!
	}
	dfs(0);
	cout << ans << "\n";
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int C;
	cin >> C;
	for (; C--;) {
		solve();
	}
}