2112. [모의 SW 역량테스트] 보호 필름

극단적인 조건으로 빠르게 종료시키는 걸 생각하기 어렵다
늘 최선의 방법을 생각해보자
백트래킹을 활용하자

#include <iostream>
#include <vector>
#include <queue>
#define MIN 987654321
#define Min(a,b) (a>b ? b:a)
using namespace std;

int TC,d,w,k;
vector<int> mak[14];
vector<int> cp_mak[14];
bool check[13];
int result;

void Init() {
	for (int i = 0; i < 14; i++) {
		mak[i].clear();
		cp_mak[i].clear();
	}
	for (int i = 0; i < 13; i++) {
		check[i] = false;
	}
	result = MIN;
}
void Print(queue<int> &q) {
	int qSize = q.size();
	while (qSize--) {
		cout << q.front();
	}
}
bool Test(vector<int> v[]) { //들어오는 v는 막
	bool flag;
	for (int j = 0; j < w; j++) {
		flag = false;
		int cntA = 0;
		int cntB = 0;
		for (int i = 0; i < d; i++) {
			//A일때
			if (v[i][j] == 0) {
				cntA++;
				cntB = 0;
			}
			//B일때
			else {
				cntA = 0;
				cntB++;
			}
			//K성능에 부합하는 순간 다른 막으로 검사 시작
			if (cntA == k || cntB == k) {
				flag = true;
				break;
			}
		}
		if (!flag)
			return false;
	}
	if (flag)
		return true;
	
}

void Change(int row, int type, bool trueOrFalse) {
	if (trueOrFalse) {
		for (int i = 0; i < w; i++) {
			cp_mak[row][i] = type;
		}
	}
	else {
		for (int i = 0; i < w; i++) {
			cp_mak[row][i] = mak[row][i];
		}
	}
}

void dfs(int start, int cnt) {
	//성능평가 깊이 보다 cnt가 많아지면 말이 안됌.
	if (cnt > k || cnt >= result) {
		return;
	}
	if (Test(cp_mak)) {
		//cout << "start:" << start << " cnt:" << cnt << endl;
		result = Min(result, cnt);
		return;
	}
	for (int i = start; i < d; i++) {
		check[i] = true;
		for (int j = 0; j < 2; j++) { //해당 막, A or B로 true
			Change(i, j, true);
			dfs(i+1, cnt + 1);
			Change(i, j, false);
		}
		check[i] = false;
	}
}

int main() {
	cin >> TC;
	for (int tc = 1; tc <= TC; tc++) {
		Init();
		cin >> d >> w >> k;
		for (int i = 0; i < d; i++) {
			for (int j = 0; j < w; j++) {
				int cell;
				cin >> cell;
				mak[i].push_back(cell);
				cp_mak[i].push_back(cell);
			}
		}
		if (k == 1 || Test(mak)) {
			cout << "#" << tc << " " << 0 << '\n';
		}
		else {
			dfs(0, 0); //몇번째 막, cnt /  조합구하기
			cout << "#" << tc << " " << result << '\n';
		}

	}

}