2112. 보호 필름

모든 경우의 수를 검사해야 한다. 

여러가지 방법이 있겠지만 비트마스크와 bfs를 사용해서 풀었다.

#include <iostream>
#include <memory.h>
using namespace std;
#define mod 600000
 
struct p {
    // x = 비트마스크. 표시된 곳을 이미 처리했다는 의미
    int x, cnt, idx;
};
 
int arrs[mod][20], D, W, K;
// queue
p q[mod];
 
bool check(int arr[20]) {
    // tt = K개의 연속한 비트. 
    int tt = (1 << K) - 1, f;
    for (int i = 0; i < W; ++i) {
        f = 0;
        for (int j = 0; j <= D - K; ++j) {
            int temp = arr[i] & (tt << j);
            // &해서 tt가 그대로 나오면 1이 K개 연속, 모두 0이면 0이 3개연속
            if (temp == (tt << j) || temp == 0) {
                f = 1;
                break;
            }
        }
        if (!f) return false; 
    }
    return true;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int t, a[20], i, j;
    int aidx, qs, qe;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc) {
        memset(a, 0, sizeof(a));
        cin >> D >> W >> K;
        // 입력받으면서 비트마스크를 만든다
        for (i = 0; i < D; ++i) for (int j = 0; j < W; ++j) {
            int temp;
            cin >> temp;
            a[j] = (a[j] << 1) | temp;
        }
        for (i = 0; i < W; ++i) arrs[0][i] = a[i];
        qs = qe = aidx = 1;
        
        cout << "#" << tc << " ";
        
        if (check(arrs[0])) {
            cout << "0\n";
        }
        else {
            int maxp = 1 << D, f = 1, ans = K;
 
            // i 원소부터 시작하는 항 만들기
            for (i = 1; i < maxp; i <<= 1) {
                int nx = i;
                for (j = 0; j < W; ++j) arrs[aidx][j] = a[j] & ~i;
                if (check(arrs[aidx])) {
                    ans = 1;
                    break;
                }
                if (!(nx & 1)) {
                    q[qe++] = { nx,1,aidx };
                    aidx++;
                }
 
                for (j = 0; j < W; ++j) arrs[aidx][j] = a[j] | i;
                if (check(arrs[aidx])) {
                    ans = 1;
                    break;
                }
                if (!(nx & 1)) {
                    q[qe++] = { nx,1,aidx };
                    aidx++;
                }
            }
 
            while (qs<qe && f) {
                int x = q[qs].x;
                int cnt = q[qs].cnt;
                int idx = q[qs++].idx;
                
                if (cnt != K - 1) {
                    // i = x의 최하위 비트. 그 아래만 순회한다
                    for (i = (x&-x) >> 1; i; i >>= 1) {
                        int nx = x | i;
                        // &~i = i 비트를 0으로 만들어 본다
                        for (j = 0; j < W; ++j) arrs[aidx][j] = arrs[idx][j] & ~i;
                        if (check(arrs[aidx])) {
                            ans = cnt + 1;
                            f = 0;
                            break;
                        }
                        if (!(nx & 1)) {
                            q[qe++] = { nx,cnt + 1,aidx };
                            aidx++;
                        }
                        // | i = i 비트를 1로 만들어 본다
                        for (j = 0; j < W; ++j) arrs[aidx][j] = arrs[idx][j] | i;
                        if (check(arrs[aidx])) {
                            ans = cnt + 1;
                            f = 0;
                            break;
                        }
                        if (!(nx & 1)) {
                            q[qe++] = { nx,cnt + 1,aidx };
                            aidx++;
                        }
                    }
                }
                else break;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}