소풍
문제 해석
- 조건에따라 N명의 학생들 중 K명의 학생들을 선발하는 문제입니다.
- 친구관계에 대한 정보 F가 주어졌을 때, 선발된 K명의 학생들은 모두 친구여야 합니다.
- N <= 900, K <= 62, F <= 5600
설계(10)
- 전형적인 백트래킹 문제입니다.
- 먼저, 친구에 대한 정보를 바로 얻을 수 있는 인접행렬을 저장해 놓습니다.
- 1번친구부터 N번까지 탐색하는데, 각각 벡터에 저장된 추가된 사람들과 친구인지 체크한 후에 모두 친구인 경우 벡터에 추가하도록 구현합니다.
- 백트래킹함수의 매개변수에 cnt 변수를 사용하여 K개의 친구가 추가되는 즉시 프린트를 하고 possible 전역변수를 이용하여 백트래킹 함수를 빠져나오도록 구현하였습니다.
- 시간복잡도를 대강 계산해보면 최악의 경우에, 900x1 + 899x2 + … + 848x62 = 약1.6x10^6정도로 시간안에 실행이 가능합니다.
구현(20)
코드
#include <iostream>
#include <vector>
using namespace std;
#define MAXN 900
int adj[MAXN][MAXN];
bool used[MAXN];
vector<int> vt;
int K,N,F;
bool possible = false;
void backtrack(int cur, int cnt){
// 조건에 맞는 친구관계를 찾았을 때, 백트래킹 함수를 빠져나오게 합니다.
if (possible) return;
if (cnt == K){
possible = true;
for (int i = 0; i < K; i++){
cout << vt[i]+1 <<"\n";
}
return;
}
for (int i = cur; i < N; i++){
if (used[i]) continue;
bool flag = false;
// 인덱스 i가 저장된 vt안의 사람들과 모두 친구인지 확인합니다.
for (int j = 0;j < cnt; j++){
if (!adj[i][vt[j]]){
flag = true;
break;
}
}
// 만약 모두 친구가 아니면 이용하지 않습니다.
if (flag) continue;
used[i] = true;
vt.push_back(i);
backtrack(i,cnt+1);
used[i] = false;
vt.pop_back();
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>> K >> N >> F;
while (F--){
int u,v;
cin >> u >> v;
// 인덱스가 0부터 시작하도록 1씩 감소시켜줍니다.
u--;
v--;
// 친구 관계 인접행렬에 저장합니다.
adj[u][v] = 1;
adj[v][u] = 1;
}
backtrack(0,0);
if (!possible){
cout << "-1\n";
}
return 0;
}
디버깅
- 조건에 맞는 친구들을 찾았을 경우 바로 출력하지 않고 백트래킹 함수를 빠져나오고 해당 관계를 출력해서 WA가 나왔습니다.
- 백트래킹 함수를 빠져나올 때, vt에 저장된 값들이 pop_back되기 때문에 정확한 답을 출력할 수 없습니다.
- 이러한 에러를 방지하기 위해서 친구관계를 모두 찾는 즉시 출력하는 방식으로 변경하였습니다.
제출결과
- 16ms
마무리
- 전형적인 백트래킹 문제였습니다. 가지치기를 하지 않아도 시간안에 해결이 가능한 문제여서 어렵지 않았던 것 같습니다.