[종만북 문제] 소풍 (문제 ID : PICNIC, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 재귀 + 완전 탐색으로 풀 수 있다.

---

[종만북 문제] 소풍 (문제 ID : PICNIC, 난이도 : 하)

이번 문제도 일단, 완전 탐색으로 풀 수 있는 문제이긴 하다. 거기에 약간의 재귀가 필요한데... 일단 소스 코드부터 첨부해 보겠다.

#include <iostream>
#include "stdlib.h"
#include <vector>

using namespace std;

int N;
vector<pair<int, int>> pairs;
int ans;

void makeGroup(vector<bool>& visit, int cur, int len)
{
	if (len == N)
	{
		ans += 1;
		return;
	}

	// check candidates starting from cur
	for (int i = cur; i < pairs.size(); ++i)
	{
		int l = pairs[i].first;
		int r = pairs[i].second;

		if (visit[l] || visit[r])
			continue;

		visit[l] = true;
		visit[r] = true;

		makeGroup(visit, i + 1, len + 2);
		
		visit[l] = false;
		visit[r] = false;
	}
}

void sol()
{
	ans = 0;

	vector<bool> visit(N, false);
	makeGroup(visit, 0, 0);

	cout << ans << endl;
}

void inputHandler()
{
	cin >> N;
	int friends = 0;
	cin >> friends;

	pairs.clear();
	for (int i = 0; i < friends; ++i)
	{
		int l, r;
		cin >> l;
		cin >> r;
		pairs.push_back({ l, r });
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		sol();
	}

	return 0;
}

 

그런데 책에 나온 재귀 호출 코드는 더욱 깔끔하다 ㅋㅋ

그렇다면 답의 상한은 어떨까?

사람은 10명까지 이고, 이때 모든 학생이 친구라면 경우의 수가 제일 많이 나올 것이다. 이 경우, 최종 답의 갯수는 9 * 7 * 5 * 3 * 1 = 945 가 된다는 것을 알 수 있다. 😁