2112 보호 필름

1. 약품 칠하는 칸이 k개가 넘지 않도록 백트래킹 한다.

2. 모든 경우에 대해 타당한지 확인 후 최소값 출력한다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int t, d, w, k, res;
int map[14][21];
bool check[14];
 
void printAll() {
    cout << endl;
    for (int i = 1; i <= d; i++) {
        if (check[i]) cout << "o ";
        else cout << "x ";
    }
    cout << endl;
}
 
bool isOK(int n) {
    int a, b;
    bool flag;
    if (n == 0) {
        for (int i = 1; i <= w; i++) {
            a = 0;
            b = 0;
            flag = false;
            for (int j = 1; j <= d; j++) {
                if (map[j][i] == 0 || check[j]) {
                    a++;
                    b = 0;
                }
                else if (map[j][i] == 1) {
                    b++;
                    a = 0;
                }
                if (a == k || b == k) {
                    flag = true;
                    break;
                }
            }
            if (!flag) return false;
        }
    }
    else {
        for (int i = 1; i <= w; i++) {
            a = 0;
            b = 0;
            flag = false;
            for (int j = 1; j <= d; j++) {
                if (map[j][i] == 1 || check[j]) {
                    b++;
                    a = 0;
                }
                else if (map[j][i] == 0 || check[j]) {
                    a++;
                    b = 0;
                }
                if (a == k || b == k) {
                    flag = true;
                    break;
                }
            }
            if (!flag) return false;
        }
    }
    return true;
}
 
void dfs(int idx, int cnt) {
    if (cnt == k + 1 || cnt >= res) return;
 
    check[idx] = true;
 
    if (isOK(0) || isOK(1)) {
        res = min(res, cnt);
        //printAll();
    }
    for (int i = idx + 1; i <= d; i++) {
        dfs(i, cnt + 1);
    }
 
    check[idx] = false;
}
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
 
    cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        cin >> d >> w >> k;
        for (int i = 1; i <= d; i++) {
            for (int j = 1; j <= w; j++) {
                cin >> map[i][j];
            }
        }
 
        res = 987654321;
        dfs(0, 0);
 
        cout << "#" << tc << " " << res << endl;
    }
}