[ 백준 2026 ] 소풍 (C++)

백준의 소풍(2026) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) N명 중에 K명을 뽑는 조합 과정을 통해서 모두 뽑은 후에, 그 K명끼리 서로 친구인지 확인해서 서로 친구가 맞다면 정답을

   도출해 내는 문제이다.

   먼저, 이 문제는 조합을 통해서 구현하는 문제인데, 조합을 잘 모른다면 아래의 링크를 타고 익혀서 오도록 하자 !

   [ 조합 구현하는 법 알아보기(Click) ! ]

  

   문제를 해결하는 전체적인 순서부터 알아보자.

   1. 전체 N명 중에서 K명을 뽑기(조합 구현)

   2. K명이 모두 서로 친구라면 정답 출력 !

   3. K명이 모두 서로 친구가 아니라면 백트래킹을 통해, 다른 K명을 뽑기 !

   이다. 하지만, 이렇게 구현하게 되면 시간초과가 나게 된다. 이를 어떻게 해결할지 알아보자.

2) 문제를 푸는 방식부터 알아보자. 본인은, 1번부터 N번까지의 순서대로, 첫 번째 뽑는 경우로 생각하고 구현하였다.

   즉, 1번을 뽑은 후, K-1명 뽑기 → 정답이 안된다면 2번을 처음으로 뽑은 후, K-1명 뽑기... 이런식으로 !

   여기서 시간을 줄이기 위해서 조건 하나를 걸어주었다.

   처음으로 뽑는 지금 이 번호의 친구의 수가 K명 이하라면 ?? 이 경우는 해봐야할까??  안해봐도 된다.

   예를 들어서 이런 경우가 있다고 생각해보자.

   1번의 친구 수 = 3명 / 2번의 친구 수 = 2명 / 3번의 친구수 = 5명 / 4번의 친구 수 = 4명 이 있는데, 이 때

   소풍을 갈 3명의 친구를 뽑아라 ! 라고 했을 때, 2번을 처음으로 뽑는 경우가 의미가 있는지 생각해보자.

   2번과 친구인 사람은 2명 뿐이다. 결국 어떻게 어떻게 3명을 뽑는다 하더라도, 결국 최소 한 명은 2번과 친구가 아닐 것이다.

   이 경우를 걸러주기 위해서, 본인은 입력받을 때 각 번호의 친구의 수를 저장해주는 배열을 하나 사용하였다.

   (본문 배열 : Friend_Num[] ; Friend_Num[a] = b 의 의미는 a번 학생의 친구의 수는 b명입니다)

  

3) 2)에서 말한대로, 우리가 시작점으로 잡은 친구는 최소한 K명의 친구는 가지고 있는 친구일 것이다. 이 후, 시작점으로 잡은

   친구의 친구들을 방문하면서, 선택을 해야하는데, 일반 조합처럼 아직 선택하지 않았다면 선택하겠습니다 ! 라는 조건과 함께

   조건을 하나 더 걸어주었다.

   바로, 그 친구를 소풍갈 친구로 선택했을 때, 그 친구와 현재 선택된 친구들이 모두 친구인지를 확인해 주었다.

   즉, K명을 모두 고르고 서로 친구인지를 확인하는 것이 아니라, 고르기 전에, 현재까지 골라놓은 친구들과 관계를 비교해서

   모두 다 친구라면, 그 학생을 고르는 방식으로 구현하였다.

4) 말이 너무 복잡하게 되어있는 것 같다. 마지막으로 깔끔하게 구체적으로 구현하는 순서를 정리해보고 소스코드를 참고하도록 하

   자.

1. 입력받으면서, 친구관계를 저장해두고, 각 학생들마다 친구 수를 저장해주자 !

   → 본인은 친군관계를 저장하기 위해서 Friend[][] 2차원 bool형 배열을 사용하였다.

      Friend[a][b] = true 의 의미는 a와b는 서로 친구입니다 를 의미한다. 또한, 양방향 관계이므로 동시에 Friend[b][a] = true도

      설정해줘야 한다. 친구 수를 저장해주는 배열을 Friend_Num[] 배열을 사용해 주었다.

2. 조합을 구할 때, 시작점이 될 친구를 고르자. 이 때, 시작점이 될 친구의 수가 K-1명보다 작다면, 이 친구는 애초에

   소풍을 갈 수가 없기 때문에 걸러줘야 한다 !

3. K명을 조합으로 뽑자 ! 이 때, 누군가를 뽑기 전, 그 학생을 뽑았을 때, 이전에 뽑힌 친구들과 모두 친구인지 아닌지

  확인해주자 ! 이전에 뽑힌 친구들 중 한명이라도 친구가 아니라면, 그 조합은 의미가 없어지기 때문에 시간낭비일 뿐이다

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
 
#define endl "\n"
#define MAX 901
using namespace std;
 
int K, N, F;
int Friend_Num[MAX];
bool Friend[MAX][MAX];
vector<int> Answer;
bool Select[MAX];
bool Flag = false;
 
void Input()
{
    cin >> K >> N >> F;
    for (int i = 0; i < F; i++)
    {
        int a, b;
        cin >> a >> b;
        Friend[a][b] = true;
        Friend[b][a] = true;
 
        Friend_Num[a]++;
        Friend_Num[b]++;
    }
}
 
void Print()
{
    for (int i = 1; i <= N; i++)
    {
        if (Select[i] == true) cout << i << endl;
    }
}
 
bool CanSelect(int x)
{
    for (int i = 1; i <= N; i++)
    {
        if (Select[i] == true)
        {
            if (Friend[x][i] == false) return false;
        }
    }
    return true;
}
 
void DFS(int Cur, int Cnt)
{
    if (Flag == true) return;
    if (Cnt == K)
    {
        Print();
        Flag = true;
        return;
    }
 
    for (int i = Cur + 1; i <= N; i++)
    {
        if (Friend[Cur][i] == false) continue;
        if (CanSelect(i) == false) continue;
        Select[i] = true;
        DFS(i, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (Friend_Num[i] < K - 1) continue;
        if (Flag == true) break;
        
        Select[i] = true;
        DFS(i, 1);
        Select[i] = false;
    }
 
    if (Flag == false) cout << -1 << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}