백준 2026번. 소풍(c++) / 백트래킹

자칫 조합으로 그냥 풀다가는 바로 시간초과가 나버리는 문제이다.

이유는, 백트래킹으로 하나씩 확인하면서 하게 되면 바로 다른 경우로의 탐색이 가능하지만

조합으로 하나씩 확인해나가면 가지치기가 확실하게 되지 않기 때문에 그 만큼 시간단축을 할 수 없게 되기 때문이다.

 

따라서, 한 사람씩 기존에 있는 사람들과 모두 친구관계인지 확인하면서 조합을 해나갔다.

 

 

코드 첨부

// 소풍
#include <iostream>
using namespace std;
 
int k, n, f, a, b;
int visited[902] = {0, };
int relation[902][902] = {0, };
bool check = false; // 맨 처음 구한 값 후에는 return 하기 위해
 
// 서로 친구인 관계인지 확인
bool Check(int idx)
{
    for(int i=1; i<=n; i++){
        if(visited[i]==true){
            if(relation[i][idx]==0){
                return false;
            }
        }
    }
    return true;
}
 
void combin(int num, int idx)
{
    if(check==true) return;
    if(num==k){
        check = true;
        for(int i=1; i<=n; i++){
            if(visited[i]==true){
                cout<<i<<"\n";
            }
        }
        return;
    }
 
    for(int i=idx+1; i<=n; i++){
        if(!visited[i] && (num+n-i+1)>=k && (relation[idx][i]==1 || relation[i][idx]==1)){
            if(Check(i)==false) continue;
            visited[i] = true;
            combin(num+1, i);
            visited[i] = false;
        }
    }
}
 
int main()
{
    cin>>k>>n>>f;
    for(int i=0; i<f; i++){
        cin>>a>>b;
        relation[a][b] = 1;
        relation[b][a] = 1;
    }
 
    // n개 중 k개를 선택하기 위해 하나의 점 선택
    for(int i=1; i<=n; i++){
        if(check==true) break;
        if(!visited[i] && (n-i+1)>=k){
            visited[i] = true;
            combin(1, i);
            visited[i] = false;
        }
    }
 
    if(check==false){
        cout<<"-1"<<"\n";
    }
 
    return 0;
}

 

 

문제 첨부

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

2026번: 소풍