백준 2026번: 소풍 (C++)

1. 문제 링크

2026번: 소풍

2. 소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_SIZE 910
using namespace std;
int n, k, f, cnt = 0;
bool matrix[MAX_SIZE][MAX_SIZE] = { false, };
bool found = false;
vector<int> ans;
vector<int> friend_num;
void dfs(int index, int cnt) {
	if (found)return;//첫 번째 답만 출력해야 함
	if (cnt >= k) {
		for (auto e : ans)cout << e << '\n';
		found = true;
		return;
	}
	bool fail;
	for (int i = index + 1; i <= n; i++) {
		fail = false;
		if (friend_num[i] >= k - 1) {
			//기존멤버들과도 친구인지 확인 필요
			for (auto e : ans) {
				if (!matrix[e][i]) { 
					fail = true; 
					break;
				}
			}
			if (!fail) {
				ans.push_back(i);
				dfs(i, cnt + 1);
				ans.pop_back();
			}
		}
	}
	return;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> k >> n >> f;
	friend_num.resize(n + 1, 0);
	int temp1, temp2;
	for (int i = 0; i < f; i++) {
		cin >> temp1 >> temp2;
		matrix[temp1][temp2] = true;
		matrix[temp2][temp1] = true;
		friend_num[temp1]++;
		friend_num[temp2]++;
	}
	for (int i = 1; i <= n - k+1; i++) {
		//n-k+1~n번째까지가 n-n+k-1+1=k명
		if (friend_num[i] >= k - 1) {
			ans.push_back(i);
			dfs(i, 1);
			ans.pop_back();
		}
	}
	if (!found)cout << -1;
	return 0;
}

3. 노트

3-1.조합을 이용한 첫 번째 시도 (시간 초과)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, f;
int main() {
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> k >> n >> f;
	vector<int> com(n, 0);
	for (int i = 0; i < k; i++) {
		com[i] = 1;
	}
	vector<int> friend_num(n, 0);
	vector<vector<int>> matrix;
	int temp1, temp2;
	for (int i = 0; i < n; i++)matrix.push_back(vector<int>(n));
	for (int i = 0; i < f; i++) {
		cin >> temp1 >> temp2;
		matrix[temp1 - 1][temp2 - 1] = 1;
		matrix[temp2 - 1][temp1 - 1] = 1;
		friend_num[temp1 - 1]++;
		friend_num[temp2 - 1]++;
	}
	bool fail = false;
	int size = 0;
	do {
		fail = false;
		size = 0;
		//서로 친구인지 체크
		for (int i = 0; i < n - 1; i++) {
			for (int j = i + 1; j < n; j++) {
				if (com[i] && com[j]) {
					if (friend_num[i] < k-1 || friend_num[j] < k-1) { fail = true; break; }
					if (matrix[i][j] != 1) { fail = true; break; }
				}
			}
		}
		if (fail == false) {
			for (int i = 0; i < n; i++) {
				if (com[i] == 1)cout << i + 1 << '\n';
			}
			return 0;
		}
	} while (prev_permutation(com.begin(), com.end()));
	cout << -1;
	return 0;
}

첫 시도에는 permutation을 이용하여 모든 가능한 조합을 오름차순으로 탐색하였다.1234,1235,...이런 식으로!하지만 최악의 경우 조합을 뽑는 데에만900C62=5384097322760089705470684302458589239017653548575164255100730173122074266877742146291162413576000번의 연산이 필요하니 시간초과가 날 수밖에 없다...

3-2.백트래킹(dfs)

i번째에서 dfs를 시작하면 i+1번째부터 탐색하여 친구관계인지 본 후, 친구관계가 맞다면 그 인덱스를 ans에 추가하고 그 인덱스부터 다시 dfs를 시작하였다. 이 때 ans에 인덱스를 추가할 때마다, 기존 ans들의 멤버들과도 친구인지 확인해야 한다.
이 때 애초에 친구 수가 k-1명 이하이면 dfs를 하지 않아 시간을 단축하였다. 또한 dfs는 1번째부터 n-k+1번째까지만 실행하면 된다. n-k째부터는 그 이후 순번들이 모두 서로 친구더라도 모임의 수가 k-1이기 때문에 조건을 충족할 수 없기 때문이다.
모임의 수가 k인 첫 번째 답만 출력하고, 그 이후 답은 출력하지 않아야 한다.