[BOJ/백준][Gold3] 1278 : 연극 (C++)

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

1278번: 연극

 

 

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

[풀이]
N이 17밖에 되지 않기 때문에 백트래킹 함수의 인자로 비트마스크를 전달해서
현재 연극에 몇번 사람이 참여하고 있는지 체크할 수 있고, 비트연산을 이용해
한명씩 추가하거나 뺄 수 있습니다.
visit 배열을 선언하여 체크한 비트마스크는 체크를 해서 중복해서 방문하지 않도록 해줍니다.

 

#include <cstdio>
#include <vector>
using namespace std;
int N,visit[1000000],ansn;
vector<int> cur,ans;
void sol(int n,int m){
    if(n!=0&&m==0&&n>ansn){
        ansn=n;
        ans=cur;
        return;
    }
    for(int i=0;i<N;i++){
        if(((1<<i)&m)>0){
            int k=(~(1<<i))&m;
            if((n!=0&&k==0)||!visit[k]){
                visit[k]=1;
                cur.push_back(i);
                sol(n+1,k);
                cur.pop_back();
            }
        }
        if(((1<<i)&m)==0){
            int k=(1<<i)|m;
            if(!visit[k]){
                visit[k]=1;
                cur.push_back(i);
                sol(n+1,k);
                cur.pop_back();
            }
        }
    }
}
int main(){
    scanf("%d",&N);
    sol(0,0);
    printf("%d\n",ansn-1);
    for(auto a : ans) printf("%d ",a+1);
}

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