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

---

 

문제풀이

 

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

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

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

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

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

---

코드

cpp

#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;
}