백준 2026 소풍

 

#include <stdio.h>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
void fast_io() {
  cin.tie(0)->sync_with_stdio(0);
}
int K,N,F;
bool chk[901][901];
bool solve=false;
int arr[63];
void dfs(int now){
    if(solve) return;
    if(now==K){
        solve=true;
        for(int x=0;x<K;x++) cout<<arr[x]<<'\n';
        return;
    }
    if(now==0){
        for(int x=1;x<=N;x++){
            arr[0]=x;
            dfs(now+1);
        }
    }
    else{
        for(int x=arr[now-1]+1;x<=N;x++){
            bool chk2=true;
            for(int y=0;y<now;y++){
                if(!chk[x][arr[y]]) chk2=false;
            }
            if(chk2){
                arr[now]=x;
                dfs(now+1);
            }
        }
    }
}
int main(){
    fast_io();
    cin>>K>>N>>F;
    for(int x=0;x<F;x++){
        int src,dst;
        cin>>src>>dst;
        chk[src][dst]=true;
        chk[dst][src]=true;
    }
    dfs(0);
    if(!solve) cout<<-1;
}

http://www.acmicpc.net/problem/2026 

2026번: 소풍

재귀를 이용해 푸는 문제였습니다.

친구관계는 상호적이기때문에 어떤 특정 K개의 학생으로 이루어진 친구관계가 존재할경우 정답이 될 수 있는 친구관계는 순서가 정해져있게됩니다. 또한 현재 I명의 학생들이 서로 친구관계라고 할때 다른 학생 A가 I명과 친구일경우 I+1명의 친구관계가 생기게 됩니다. 이를 이용해서 재귀적으로 구현하면 됩니다.