[SWEA] 보호 필름

[SWEA] 보호 필름

Problem URL : 보호 필름

#include <iostream>
#include <cstring>

int film[13][20];
int d, w, k;
int answer;

bool check() {

	for (int W = 0; W < w; W++) {
		int sum ;
		for (int D = 0; D < d; D++) {
			if (D == 0 || (film[D][W] != film[D - 1][W])) {
				if ((d - D) < k) {
					// 하나의 열이라도 통과하지 못하면 false
					return false;
				}
				sum = 1;
			} else {
				sum++;
				if (sum >= k) {
					break;
				}
			}
		}
	}

	return true;
}

bool dfs(int D, int count) {
	if (D >= d && count != 0) {
		return false;
	}

	if (count == 0) {
		return check();
	}

	// D행 데이터를 임시 저장
	int tmpRow[20];
	for (int W = 0; W < w; W++) {
		tmpRow[W] = film[D][W];
	}

	// D행을 0으로 색칠
	for (int W = 0; W < w; W++) {
		film[D][W] = 0;
	}
	if (dfs(D + 1, count - 1)) {
		return true;
	}

	// D행을 1으로 색칠
	for (int W = 0; W < w; W++) {
		film[D][W] = 1;
	}
	if (dfs(D + 1, count - 1)) {
		return true;
	}

	// D행을 아무것도 안하고 건너뜀
	for (int W = 0; W < w; W++) {
		film[D][W] = tmpRow[W];
	}
	if (dfs(D + 1, count)) {
		return true;
	}

	return false;
}

int main() {
	int TC;
	scanf("%d", &TC);
	for (int tc = 1; tc <= TC; tc++) {
		scanf("%d %d %d", &d, &w, &k);
		for (int D = 0; D < d; D++) {
			for (int W = 0; W < w; W++) {
				scanf("%d", &film[D][W]);
			}
		}
		answer = k;
		if (k != 1) {
			for (int i = 0; i < k; i++) {
				if (dfs(0, i)) {
					answer = i;
					break;
				}
			}
		} else {
			answer = 0;
		}
		printf("#%d %d\n", tc, answer);
	}

	return 0;
}