백준 2026 (소풍) c++

문제

2026번: 소풍

총 학생수 n명 중에서 f개의 친구관계를 바탕으로 k명의 학생을 뽑아 소풍을 데려가는 문제입니다.

1. 먼저 한 학생을 대상으로 그 친구관계를 살펴봅니다.

2. 대상 학생의 친구의 친구 관계를 살펴보고 대상 학생과 친구가 될 수 있는지 살펴 봅니다.

2를 반복하다가 조건이 안맞으면 1의 대상학생을 다시 선택해 반복해 주면 됩니다.

여기서 friend_num[] 이라는 배열을 설정해줄건데 friend_num[3] = 4 라는 의미는 3번 학생이 4명의 친구를 가진다는

의미입니다.

따라서 friend_num[i] < k-1 이면 문제에서 원하는 친구의 수를 가지지 못하므로 아예 배제 시키고 생각해도 됩니다.

for (int f1, f2,i = 0; i < f; i++) {
        cin >> f1 >> f2;
        check[f1][f2] = true;
        check[f2][f1] = true;
        friend_num[f1]++;
        friend_num[f2]++;
    }
    for (int i = 1; i <= n; i++) {
        if (friend_num[i] < k - 1)
            continue;
        chingu[i] = true;
        recursion(i, 1);
        chingu[i] = false;
    }

check 함수는 bool 형이고 두개의 인덱스가 서로 친구관계인것을 알려줍니다.

check[1][2] = true : 1번과 2번이 친구 관계라는 의미입니다.

chingu 함수는 bool 형이고 지금까지 선택한 친구를 저장하는 배열입니다.

chingu[1], chingu[3], chingu[5] 가 모두 true면 3명 모두 서로 친구라는 의미입니다.

void recursion(int start, int cnt) {
    if (cnt == k) {
        for (int i = 1; i <= n; i++) {
            if (chingu[i])
                cout << i  << '\n';
        }
        exit(0);
    }
 
    for (int i = start+1; i <= n; i++) {
        if (!check[start][i]) continue;
        if (!canselect(i))continue;
        chingu[i] = true;
        recursion(i, cnt + 1);
        chingu[i] = false;
    }
}

recursion 함수의 첫번째 인자는 현재 선택한 친구고 두번쨰 인자는 지금까지 선택한 친구의 명수 입니다.

2번쨰 줄에서 볼 수 있듯이 cnt=k 이면 문제에서 요구하는 친구의 명수를 모두 선택한것이므로 출력해주고 종료합니다.

10번째 줄에서 시작하는 for문에서 canselect 함수는 지금 선택할 친구가 이전의 선택한 친구와 친구관계인지 확인

하는 함수 입니다.

bool canselect(int x) {
    for (int i = 1; i <= n; i++) {
        if (chingu[i])
            if (!check[x][i])return false;
    }
    return true;
}

친구로 선택할려고하는 x라는 친구가 지금까지 선택해왔던 친구와 서로 친구관계면 true를 출력, 그게아니면 false

입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int n, k, f;
bool check[901][901];
int friend_num[901];
bool chingu[901];
void recursion(int start, int cnt);
bool canselect(int x);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> k >> n >> f;
 
    for (int f1, f2,i = 0; i < f; i++) {
        cin >> f1 >> f2;
        check[f1][f2] = true;
        check[f2][f1] = true;
        friend_num[f1]++;
        friend_num[f2]++;
    }
    for (int i = 1; i <= n; i++) {
        if (friend_num[i] < k - 1)
            continue;
        chingu[i] = true;
        recursion(i, 1);
        chingu[i] = false;
    }
 
    cout << -1;
 
    return 0;
}
void recursion(int start, int cnt) {
    if (cnt == k) {
        for (int i = 1; i <= n; i++) {
            if (chingu[i])
                cout << i  << '\n';
        }
        exit(0);
    }
 
    for (int i = start+1; i <= n; i++) {
        if (!check[start][i]) continue;
        if (!canselect(i))continue;
        chingu[i] = true;
        recursion(i, cnt + 1);
        chingu[i] = false;
    }
}
bool canselect(int x) {
    for (int i = 1; i <= n; i++) {
        if (chingu[i])
            if (!check[x][i])return false;
    }
    return true;
}