[C/C++] 백준 - 2026번 : 소풍

https://www.acmicpc.net/problem/2026

2026번: 소풍

문제

원장선생님께서는 1부터 N까지 번호가 붙은 N(K ≤ N ≤ 900)명의 학생들 중에서 K(1 ≤ K ≤ 62)명의 학생들을 소풍에 보내려고 한다. 그런데 원장선생님께서는 중간에 싸움이 일어나면 안되므로 소풍을 갈 학생들이 모두 서로 친구 사이이기를 원한다. 원장선생님께서는 이러한 일을 이번에 조교로 참가한 고은이에게 친구 관계에 대한 정보를 F(1 ≤ F ≤ 5,600)개를 주시며 K명을 선발하라고 부탁하였다.

고은 조교를 도와 소풍을 가게 될 K명의 학생들을 결정하시오.

 

 

*** 중간에 싸움이 나지 않기 위해 소풍을 갈 학생들은 모두 친구사이여야한다.

 

소풍에 가는 학생들은 모두 친구사이여야한다.

소풍에 가는 학생들은 모두 다른 친구를 가지고 있기에 소풍에 가는 학생 집합 안에 존재하는 모든 친구 가능 경우의 수를 확인해주어야한다. 그리고 그 집합으로는 선발하고자 하는 인원을 선발 못할 가능성이 있기에 한 명으로만 시작하는 것이 아닌 모든 인원을 시작인원으로 확인해주어야한다. 단, 문제의 조건이 답이 될 수 있는 경우가 여러 개일때 학생 번호가 작은 순으로 출력을 해야하기에 1번부터 시작하는 강제성을 부여한다.

 

즉, 재귀함수를 이용한 완전탐색을 이용하여 문제를 해결하며 순서를 강제하였기 때문에 조건에 부합하는 집합이 존재한다면 출력을 하고 프로그램을 종료한다.

 

학생을 넣고 친구 관계인지 확인하게 된다면 매우 비효율적이기 때문에 친구를 넣을 수 있는지 없는지 소풍집합 내 존재하는 친구들과 모두 친구관계인지 확인해주는 함수를 작성하여 보다 효율적으로 만들도록 하였다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000009
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int K, N, F;
bool isConnected[901][901];
vector<vector<int>> answer;

void input() {
	cin >> K >> N >> F;
	for (int i = 0; i < F; i++) {
		int first, second;
		cin >> first >> second;
		isConnected[first][second] = isConnected[second][first] = true;
	}
}

bool isValid(int who, vector<int>& ps) {
	for (auto& p : ps) {
		if (!isConnected[who][p]) 
			return false;
	}
	return true;
}

void solution(int who, int cnt, vector<int> &ps) {
	if (cnt == K) {
		for (auto& ptr : ps) 
			cout << ptr << endl;
		exit(0);
	}

	for (int i = who+1; i <= N; i++) {
		if(isValid(i, ps)) {
			ps.push_back(i);

			solution(i, cnt + 1, ps);

			ps.pop_back();
		}
	}
}

void func() {
	for (int i = 1; i <= N; i++) {
		vector<int> ps;
		ps.push_back(i);

		solution(i, 1, ps);

		ps.pop_back();
	}
	cout << -1 << endl;
}

int main() {
	fastio;
	input();
	func();

	return 0;
}