[종만북] 6장. 완전 탐색 (2) PICNIC

문제 바로가기: https://www.algospot.com/judge/problem/read/PICNIC

 

1. 중복된 답

아래 코드의 문제점은 중복된 답을 세는 경우를 처리하지 않은 점이다. 중복이 된 원인은 (0, 1)과 (1, 0)을 각각 다른 경우로 봤고 다른 순서로 학생들을 짝지어 주는 것도 서로 다르다고 카운트했기 때문이다. 

#include <bits/stdc++.h>
using namespace std;

int n;
bool graph[10][10]; // 최대 10

int countPairings(bool taken[10]) { // taken[i]: i번 학생이 짝을 찾은 경우 true
	// Base case: 전부 짝이 생기면 종료
	bool finished = true;
	for (int i = 0; i < n; i++) if (!taken[i]) finished = false;
	if (finished) return 1; 

	int ret = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			// 친구 맺어주기
			if (!taken[i] && !taken[j] && graph[i][j]) {
				taken[i] = taken[j] = true;
				ret += countPairings(taken); // 친구 생성 후 다음 재귀 호출
				taken[i] = taken[j] = false; // i랑 j가 친구지만 서로 짝이 안지어진 경우도 고려하기 위함
			}
		}
	}
	return ret;
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int c;
	cin >> c;
	while (c--) {
		int m;
		cin >> n >> m;
		
		// 무향 그래프 연결
		fill(graph[0], graph[0] + 100, 0);
		for (int i = 0; i < m; i++) {
			int a, b; cin >> a >> b;
			graph[a][b] = 1;
			graph[b][a] = 1;
		}

		bool tp[10]{ };
		cout << countPairings(tp) << "\n";
	}
}

 

2. 중복된 답 제거 

중복으로 세는 상황이 생길 때 흔히 사용하는 방법으로는 여러가지 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 방법이 있다. 여기선 학생들별로 우선순위를 정해서 해당 학생부터 짝을 지어주면 된다. 마침 학생들이 번호로 되어 있으므로, i를 0부터 n-1까지로 반복하다가 i번째 학생이 짝이 없으면 그 학생을 타깃으로 정하면 된다. 그 학생과 짝이 될 학생을 찾는 과정은 위와 동일하다.

int countPairings(bool taken[10]) { // taken[i]: i번 학생이 짝을 찾은 경우 true
	// 남은 학생들 중 가장 번호 빠른 학생 찾기 
	int firstFree = -1;
	for (int i = 0; i < n; i++) {
		if (!taken[i]) {
			firstFree = i; break;
		}
	}

	if (firstFree == -1) return 1; // Base Case: 모든 학생들 다 짝 지어짐

	int ret = 0;
	// firstFree 학생과 짝 지어줄 학생 찾기
	for (int pairWith = firstFree + 1; pairWith < n; pairWith++) {
		if (!taken[pairWith] && graph[firstFree][pairWith]) {
			taken[pairWith] = taken[firstFree] = true;
			ret += countPairings(taken); // 친구 생성 후 다음 재귀 호출
			taken[pairWith] = taken[firstFree] = false; // 이 둘이 서로 짝이 안지어진 경우도 고려하기 위함
		}
	}
	return ret;
}