[백준] [C++] 가르침 1062번

문제 설명

백트래킹을 사용하여도 풀리지만, 비트마스킹 연습을 위해 비트마스킹으로 풀어보도록 하자.

비트마스킹 풀이는 백트래킹보다 약 10배 빠르다.

단, 비트연산에 대한 기본 지식은 있어야 코드 이해가 가능하다.

2진수 표기

숫자 앞에 "0b" 를 붙인다.

cpp
int a = 0b101;  // a = 5 (1*4 + 0*2 + 1*1)
cout << a << endl;  // 5 출력

2진수로 출력

헤더파일 : #include <bitset>

bitset<비트의 개수>(출력할 변수)

cpp
int a = 5;
cout << bitset<10>(a) << endl;  // 0000000101 출력

비트마스킹을 이용한 풀이

cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define MAX

/*
비트마스킹 (백트래킹이 필요 없음)
K개의 글자를 가르칠때, 읽을 수 있는 단어의 개수

antic 는 무조건 들어가야 함 -> K<5 라면 답은 0

미리 각 단어에 대해 필요한 bit를 만들어놓고,
확인할때 현재 bit와 단어의 bit를 AND 연산을 이용해 단어의 bit와 같다면
그 단어를 만들 수 있는것이다.
*/

int N, K;
string words[50];
int wordsBit[50];
int ans;

void dfs(int bit, int level, int last){
    // K개의 글자를 가르쳤다면
    if (level==K){
        int cnt=0;
        for (int i=0; i<N; i++){
            if ((bit & wordsBit[i]) == wordsBit[i]) cnt++;
        }
        if(cnt==N){  // N개 모두 가능하면 바로 종료
            cout << N;
            exit(0);
        }
        ans = max(ans, cnt);  // ans 업데이트
    }

    // 아직 확인 안한 비트 중에 현재 안켜져있는 비트에 대해 dfs
    for (int i = last+1; i < 26; ++i){
        // i번 비트가 0이라면 켜주고 재귀
        if (!(bit & (1 << i)))
            dfs(bit | (1 << i), level + 1, i);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> K;
    for (int i=0; i<N; i++){
        cin >> words[i];
    }

    // 5개 미만이면 절대 못만들음
    if (K<5) {
        cout << 0;
        exit(0);
    }

    int bit = 0b00000010000010000100000101;  // 2진수로 a, c, i, n, t 켜줌

    // 미리 각 단어에 대해 필요한 bit를 만들어놓기
    for (int i=0; i<N; i++){
        wordsBit[i] = 0b00000010000010000100000101;
        string word = words[i];

        // 모든 단어는 "anta"로 시작되고, "tica"로 끝나니까 그 사이만
        for (int j=4; j<word.length()-4; j++){
            wordsBit[i] |= 1 << (word[j]-'a');  // 알파벳에 맞는 비트를 켜주기
        }
        // cout << bitset<26>(wordsBit[i]) << '\\n';  // 각 문자의 비트가 잘 됐는지 확인
    }

    // 이미 5개의 글자는 가르쳤으니 진행도는 5로 시작, -1은 마지막으로 체크한 비트의 인덱스
    dfs(bit, 5, -1);

    cout << ans;

    return 0;
}

제출 결과

20ms 대의 빠른 속도로 답을 구할 수 있다.

백트래킹을 사용한 다른 사람들의 속도

마무리

비트 문제를 몇개 풀다 보니 비트 연산을 활용하는 능력이 좀 생겼다.

눈으로 확인하기 힘든데, 0b와 bitset<>을 사용하면 중간에 값을 체크해볼 수 있어서 좋은 것 같다.