소풍 2026

문제

접근 방법

친구의 수가 K-1개 이상인 사람만을 탐색하면 탐색의 횟수가 줄어든다.
K-1 미만의 경우는 서로 친구를 충족할 수가 없으므로 무시하면 된다.

K개만큼의 사람을 찾아냈다면 서로가 친구인지 확인해 주고 아니면 무시하고 맞으면 출력 후 끝내주면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int K, N, F;
vector<vector<int>> graph;
vector<vector<bool>> isFriend;
vector<bool> isVisited;
vector<int> picnic;
bool friendCheck()
{
    for (int i = 0; i < picnic.size(); ++i)
        for (int j = i + 1; j < picnic.size(); ++j)
            if (!isFriend[picnic[i]][picnic[j]])
                return false;
    return true;
}
void dfs(int cur, int depth)
{
    if (K == depth)
    {
        if (friendCheck())
        {
            for (int i : picnic)
                cout << i << "\n";
            exit(0);
        }
        return;
    }
    for (int next : graph[cur])
    {
        if (graph[next].size() < K - 1 || isVisited[next])
            continue;
        isVisited[next] = true;
        picnic.push_back(next);
        dfs(next, depth + 1);
        picnic.pop_back();
        isVisited[next] = false;
    }
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> K >> N >> F;
    graph = vector<vector<int>>(N + 1, vector<int>());
    isFriend = vector<vector<bool>>(N + 1, vector<bool>(N + 1));
    isVisited = vector<bool>(N + 1);
    while (F--)
    {
        int i, j;
        cin >> i >> j;
        graph[i].push_back(j);
        graph[j].push_back(i);
        isFriend[i][j] = isFriend[j][i] = true;
    }
    for (int i = 1; i <= N; ++i)
    {
        if (graph[i].size() < K - 1)
            continue;
        sort(graph[i].begin(), graph[i].end());
    }
    for (int i = 1; i <= N; ++i)
    {
        if (graph[i].size() < K - 1)
            continue;
        isVisited[i] = true;
        picnic.push_back(i);
        dfs(i, 1);
        picnic.pop_back();
        isVisited[i] = false;
    }
    cout << -1;
    return 0;
}

풀이

번호가 작은 순으로 출력되어야 하므로 정렬을 해주는 것이 좋다.
정렬 또한 사용할 일이 없는 K-1 미만의 사람은 무시해 주면서 해주면 된다.

서로가 친구인지 확인할 때는 삼각형 모형으로 확인한다고 생각하면 된다.
이미 확인한 경우를 양방향으로 확인해 볼 필요가 없기 때문에 반만 확인하는 것이다.