BOJ 2026 - 소풍

  완전 그래프에 관한 문제다. 크기가 K인 그래프 내의 clique(클릭) 중에서 구성된 정점의 번호가 제일 작은 것을 찾으려고 한다. 입력 데이터의 규모가 작으니 하나하나 접근해나가며 완전 그래프를 만들 수 있는지 없는지 판단하는 백트래킹 재귀 함수를 만들었다.

< 사진 출처 - https://math.stackexchange.com/questions/758263/whats-maximal-clique>

  재귀 호출하기 전에, for문으로 번호가 작은 친구부터 탐색하도록 한다. 마찬가지로 재귀 내에서도 번호가 작은 친구를 찾도록 유도하여 구성된 정점의 번호가 작은 클릭을 찾을 수 있다.

  재귀 함수의 기저 사례는 현재 구성된 완전 그래프의 크기 p와 찾아야 하는 완전 그래프의 크기 k와 같으면 true를 반환, 만약 모든 친구를 검사했음에도 크기가 k인 완전 그래프를 찾지 못했다면 -1 반환하는 것으로 설정했다.

  재귀는 완전 그래프를 찾을 때까지 들어가므로 따로 vector 변수를 두어, 해당 정점을 들렸을 때, push_back하고, 탐색 실패하고 정점을 빠져나갈 때 pop_back을 하여 방문 정점을 처리한다.

#include <cstdio>
#include <vector>
using namespace std;
int N, K;
bool adj[901][901];
vector<int> back;
bool rec(int u, int p) {
	back.push_back(u);
	if (p == K) return 1;
	if (u == N-1) return 0;

	int v, i, f;
	for (v = u + 1; v<N; v++)
		if (adj[u][v]) {
			f = 1;
			for (i = 0; i < back.size() && f; i++)
				if (!adj[v][back[i]]) f = 0;
			if (f && rec(v, p + 1)) return 1;
		}
	back.pop_back();
	return 0;
}

int main() {
	int F, u,v,i,f=1;
	scanf("%d%d%d", &K, &N, &F);
	while (F--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		adj[u][v] = adj[v][u] = 1;
	}
	for(i=0;i<N;i++)
		if (rec(i, 1)) {
			for (int stk : back) printf("%d\n", stk + 1);
			f = 0;
			break;
		}
	if(f) printf("-1");
	return 0;
}