[BOJ/2026/C++] 소풍

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

문제

• 원장선생님께서는 1부터 N까지 번호가 붙은 N(K ≤ N ≤ 900)명의 학생들 중에서 K(1 ≤ K ≤ 62)명의 학생들을 소풍에 보내려고 한다.

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

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

조건

• 첫째 줄에 공백으로 분리된 세 정수 K, N, F가 주어진다. 다음 F개의 줄에는 서로 친구 관계인 두 사람의 번호가 주어진다.
• 친구 관계는 상호적인 관계이므로 2번 학생이 4번 학생을 좋아하면 4번 학생도 2번 학생을 좋아한다. 같은 친구 관계가 여러 번 주어지는 경우는 없다.

풀이

하나를 뽑은 상태에서 또 뽑는 문제이다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int K, N, F;

bool graph[901][901];
vector<int> ans;

void solve(int now)
{
  if (ans.size() == K)
  {
    for (int i = 0; i < ans.size(); i++)
    {
      cout << ans[i] << '\n';
    }
    exit(0);
  }

  for (int next = now + 1; next <= N; next++)
  {
    if (!graph[now][next])
      continue;
    bool IsFriend = true;
    for (auto i : ans)
    {
      if (!graph[i][next])
      {
        IsFriend = false;
        break;
      }
    }
    if (!IsFriend)
      break;
    ans.push_back(next);
    solve(next);
    ans.pop_back();
  }
}

int main()
{
  fastio;
  cin >> K >> N >> F;

  int a, b;

  // 친구관계 저장
  for (int i = 0; i < F; i++)
  {
    cin >> a >> b;
    graph[a][b] = graph[b][a] = true;
    graph[a][a] = graph[b][b] = true;
  }
  for (int i = 1; i <= N; i++)
  {
    ans.push_back(i);
    solve(i);
    ans.pop_back();
  }
  cout << -1 << '\n';
  return 0;
}