[백준/BOJ] 백준 2026번 : 소풍

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

2026번: 소풍

 

k명의 학생을 고르는 경우를 확인하여 문제를 해결했는데, 해당 학생을 고를지 확인할 때 지금까지 고른 학생들과 모두 친구 관계인지 확인하는 방법을 통해 확인했다. 이를 위해 이전에  friend_check[A][B]에 A학생과 B학생이 친구 관계인지 정보를 저장해 놓았다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int k, n, f;
int friend_check[905][905];
vector<int> result;
bool finish = false;

void Pre() {
	for (int i = 0; i < 905; i++) {
		for (int j = 0; j < 905; j++) {
			friend_check[i][j] = 0;
		}
	}
}

//현재 고를 학생(check_index)이 지금까지 고른 학생들과 모두 친구 관계인지 확인
bool Check(vector<int>& checked, int check_index) {

	for (int i = 0; i < checked.size(); i++) {
		if (friend_check[checked[i]][check_index] == 0) { //지금까지 고른 학생들 중 check_index학생과 친구가 아닌 학생이 있을때
			return false;
		}
	}

	return true;
}

void Solve(vector<int>& checked, int last_selected) {

	if (finish) {
		return;
	}

	//k명을 다 골랐을때
	if (checked.size() == k) {

		result = checked;
		finish = true; //끝났다고 표시

		return;
	}

	//마지막에 골랐던 학생의 다음 학생부터 고르는것을 확인한다
	for (int i = last_selected + 1; i <= n; i++) {

		//i번 학생을 고를 수 있는지 확인
		if (Check(checked, i)) {
			checked.push_back(i);
			Solve(checked, i);
			checked.pop_back();
		}
	}

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	Pre();

	cin >> k >> n >> f;

	for (int i = 0; i < f; i++) {
		int f1, f2;
		cin >> f1 >> f2;

		friend_check[f1][f2] = 1;
		friend_check[f2][f1] = 1;
	}

	vector<int> checked;
	Solve(checked, 0);

	if (finish == false) { //k명을 만들 수 없을때
		cout << -1;
	}

	else {
		for (int i = 0; i < result.size(); i++) {
			cout << result[i] << "\n";
		}
	}

	return 0;
}