[SWEA][C++] 2112 보호필름

문제

SW Expert Academy 모의 문제 2112 보호필름

풀이

열마다 k개 연속으로 A 혹은 B 보호필름이 있으면 합격입니다. 모든 열이 이 조건에 만족하려면, 최소 몇 개의 행에 투약을 해야하는지가 문제입니다. 

1. 투약 횟수를 지정해 줍니다.

2. 투약 횟수만큼 조합을 해줍니다. DFS를 이용했습니다.

3. 모든 열이 합격 기준에 만족하는지 확인합니다.

처음 구현했을 때 시간 초과가 나서 벡터를 배열로 바꾸고, 하나의 열이라도 합격 기준에 미치지 못하면 바로 빠져나오도록 최대한 가지치기했습니다. 시간 관리에 유의하면서 풀어야 하는 문제입니다.

코드

#include <iostream>
using namespace std;
int answer = 987654321;
int map[14][22];
int d, w, k;
bool isFin = false;
int list[14];
void dfs(int cnt, int valu, int res) {
	
	if (valu == res) {
		if (isFin) return;
		int val = 0;
		//연속확인
		for (int i = 1; i <= w; i++) {
			bool isOK = false;
			int start = 1;
			int tmp = 1;
			for (int j = 2; j <= d; j++) {
				if (map[j][i] == map[start][i]) {
					tmp++;
				}
				else {
					start = j;
					tmp = 1;
				}
				if (k == tmp) {
					isOK = true;
					val++;
					break;
				}
			}
			if (!isOK) break;
		}
		if (val == w) {
			cout << cnt << endl;
			isFin = true;
		}
		return;
	}
	if (cnt > d ) return;
	//투약할 위치 지정

	dfs(cnt + 1, valu, res);
	int color[21];
	for (int i = 1; i <= w; i++) {
		color[i] = map[cnt][i];
	}

	for (int i = 1; i <= w; i++) {
		map[cnt][i] = 0;
	}
	dfs(cnt + 1, valu + 1, res);

	for (int i = 1; i <= w; i++) {
		map[cnt][i] = 1;
	}
	dfs(cnt + 1, valu + 1, res);

	for (int i = 1; i <= w; i++) {
		map[cnt][i] = color[i];
	}
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		answer = 987654321;
		isFin = false;
		cin >> d >> w >> k;
		for (int i = 1; i <= d; i++) {
			for (int j = 1; j <= w; j++) {
				cin >> map[i][j];
			}
		}
		for (int r = 0; r < d; r++) {
			dfs(1, 0, r);

			if (isFin) {
				answer = r;
				break;
			}
		}
		cout << "#" << t << " " << answer << endl;
	}
}