[BOJ/백준][Gold3] 2026 : 소풍 (C++)

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

2026번: 소풍

 

 

[난이도] Gold3
[유형] 백트래킹

[풀이]
인접행렬에 친구관계를 저장 해준 뒤, 재귀를 이용한 백트래킹을 해주면 됩니다.
현재까지 확정된 친구를 frd vector에 저장해준 뒤, 현재 친구가 될 수 있는지 확인중인 친구가
이 frd vector의 친구와 모두 친구인지 확인해서, 모두 친구이면 다음 함수를 호출해줍니다.
frd vector의 크기가 K(<=62)가 되면 조건을 만족하는 친구집합을 구한 것이므로 출력하고 종료해줍니다.
frd vector의 크기가 최대 62를 넘어갈 수 없으므로 시간내에 해결이 가능합니다.

 

#include <cstdio>
#include <vector>
using namespace std;
int K,N,F,adj[901][901];
vector<int> frd;
bool sol(int cur){
    if(frd.size()==K) return 1;
    for(int i=cur+1;i<=N;i++){
        bool ok=1;
        for(auto a : frd){
            if(!adj[i][a]){
                ok=0;
                break;
            }
        }
        if(ok) {
            frd.push_back(i);
            if(sol(i)) return 1;
            frd.pop_back();
        }
    }
    return 0;
}
int main(){
    scanf("%d%d%d",&K,&N,&F);
    while(F--){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[u][v]=adj[v][u]=1;
    }
    for(int i=1;i<=N;i++){
        frd.push_back(i);
        if(sol(i)){
            for(auto f : frd) printf("%d\n",f);
            return 0;
        }
        frd.clear();
    }
    puts("-1");
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold3/2026.cpp