[백준 C++] 2026 소풍 - 백트래킹

---

 

문제풀이

 

백트래킹을 이용해서 푸는 문제입니다.

먼저 각 학생의 친구 수를 저장하는 배열과

모든 학생에 대해서 친구인지 아닌지를 저장하는 2차원 배열을 생성했습니다.

그리고 백트래킹을 이용해서 1부터 N번의 학생까지 K-1 이상의 친구를 보유한 학생을 선택해서

K명을 선택했을 때 모두 서로 친구라는 조건이 만족하면 출력 & 종료하도록 했습니다. 

---

코드

#include <iostream>
using namespace std;

int N, K, F;

int FN[901];
bool Friend[901][901];
int Sel[62];

bool Check()
{
	for (int i = 0; i < K - 1; ++i)
	{
		for (int j = i + 1; j < K; ++j)
		{
			if (!Friend[Sel[i]][Sel[j]])
			{
				return false;
			}
		}
	}

	return true;
}

void DFS(int Idx, int Num)
{
	if (Idx == K)
	{
		if (Check())
		{
			for (int i = 0; i < K; ++i)
			{
				cout << Sel[i] << '\n';
			}

			exit(0);
		}

		return;
	}

	if (Num > N)
	{
		return;
	}

	if (FN[Num] >= K - 1)
	{
		Sel[Idx] = Num;
		DFS(Idx + 1, Num + 1);
	}

	DFS(Idx, Num + 1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> K >> N >> F;

	for (int i = 0; i < F; ++i)
	{
		int A, B;
		cin >> A >> B;

		++FN[A];
		Friend[A][B] = true;

		++FN[B];
		Friend[B][A] = true;
	}
	
	DFS(0, 1);

	cout << -1;
}