[SWEA] #2112 _ 보호 필름

[보호 필름] https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

dfs를 이용하여 모든 경우의 수를 다 돌린 후, 성능 검사에 통과하는 최소 투입 수를 구한다.

dfs를 돌리는 경우는 총 세가지로 생각할 수 있다.

 

1. 약품 주입 X
2. A 약품 주입
3. B 약품 주입

 

[ 소스 코드 ]

 

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int D, W, K, injCount;
vector<vector<int> > film;

void solve(int count, int idx);
int is_pass();
int main() {
	int test_case;

	scanf("%d", &test_case);
	for (int i = 1; i <= test_case; i++) {
		scanf("%d %d %d", &D, &W, &K);
		film.assign(D, vector<int>(W, 0));
		injCount = 9999999;
		for (int j = 0; j < D; j++) {
			for (int k = 0; k < W; k++) {
				scanf("%d", &film[j][k]);
			}
		}

		if (is_pass() || K == 1) injCount = 0;
		else solve(0, 0);
		
		printf("#%d %d\n", i, injCount);
		film.clear();
	}

	return 0;
}

void solve(int count, int idx) {
	vector<int> tmp;

	if (count >= injCount) return;
	if (is_pass()) {
		injCount = min(injCount, count);
		return;
	}
	if (idx >= D || count > K) return;
	
	tmp.assign(film[idx].begin(), film[idx].end());
	solve(count, idx + 1);
	for (int i = 0; i < W; i++) film[idx][i] = 1;
	solve(count + 1, idx + 1);
	for (int i = 0; i < W; i++) film[idx][i] = 0;
	solve(count + 1, idx + 1);
	film[idx].assign(tmp.begin(), tmp.end());
	
}

int is_pass() {
	int count, pre;

	for (int i = 0; i < W; i++) {
		count = 1;
		pre = film[0][i];
		for (int j = 1; j < D; j++) {
			if (pre == film[j][i]) {
				count++;
				if (count >= K) break;
			}
			else {
				count = 1;
				pre = film[j][i];
			}
		}
		if (count < K) return 0;
	}
	return 1;
}