실패를 두려워하지 않고
될 때까지 덤비는 🔥
그런 프로그래머 😎

Happy New Year
202 5 6

문제
풀이

💡Idea

사고의 흐름

문제의 본질은, 정점이 K개 이상인 그래프를 찾는 것이다. 두가지 방식의 접근이 떠오른다.

  1. 완전 그래프틀 찾으며. -> 그 중 정점의 개수가 K개 이상인 것을 찾는다.
  2. 정점을 하나씩 모아가며, -> 완전 그래프를 이루는지 확인한다.

2번 방식이 백트래킹을 이용하면 구현이 가능할 것 같아 2번 방식으로 풀이를 진행하였다.

풀이 흐름

백트래킹을 이용하여 모든 경우의 수를 돌려본다. 즉, K명을 뽑는 모든 경우의 수를 시도한다.
당연히 시간을 줄이기 위해 가지치기를 진행한다. 방식은, 한 명씩 조건을 만족하는 지 확인하고 소풍 갈 그룹에 뽑아두는 것이다.

조건

  1. 친구가 K-1명 이상인가
  2. 기존에 뽑힌 사람들과 모두 친구인가

현재 구성원으로 K명까지 못 만든다면 마지막 구성원을 빼고 다음 구성원으로 대체한다.

🔑Code

#include <bits/stdc++.h>
using namespace std;

bool isAdj[901][901];
int edgeCnt[901];

vector<int> s;
int K, N, F;

bool func(int trial, int nxt){
    if(trial == K){
        return true;
    }
    if(nxt > N) return false;
    for(int i = nxt; i <= N ; i++){
        if(edgeCnt[i] < K-1) continue;
        bool isAdjOthers = true;
        for(int& c: s){
            if(!isAdj[i][c]){
                isAdjOthers = false;
                break;
            }
        }
        if(!isAdjOthers) continue;
        s.emplace_back(i);
        if(func(trial+1, i+1)) return true;
        s.pop_back();
    }
    return false;
}

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> K >> N >> F;

    for(int i = 0; i < F; i++){
        int u, v;
        cin >> u >> v;
        isAdj[u][v] = true;
        isAdj[v][u] = true;
        edgeCnt[u]++;
        edgeCnt[v]++;
    }
    
    if(func(0, 1)){
        for(int& c: s)
            cout << c << '\n';
    }
    else
        cout << -1;

    return 0;
}

🗨️ Side Notes

새해가 밝았다. 2026년에도 우리 모두 화이팅하자는 마음으로 2026번을 풀어보았다.
모두 새해 복 많이 받으세요 :)

참고