SW Expert Academy - 2112. 보호 필름

문제링크

• 보호 필름

문제설명

• 다음과 같은 보호필름이 주어진다.

• 위 그림은 셀 8개로 이루어진 엷은 막 6장을 쌓아서 만든 두께 6, 가로크기 8인 보호 필름의 단면을 보여준다.
• 보호필름의 성능을 검사하기 위해 합격기준 K가 주어지고, 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K 개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.

• 성능검사에 통과하기 위해서 약품을 사용할 수 있다.
• 약품은 막 별로 투입할 수 있으며 막의 모든 셀들을 하나의 특성으로 변경한다.

• 입력으로 보호필름의 두께(D), 가로크기(W), 합격기준(K)와 보호필름의 단면 정보가 주어질때, 성능검사를 통과하기 위한 최소 약품 투입 횟수를 구하라

문제접근

• 재귀호출을 이용한 완전탐색으로 풀었다. 단, 시간을 줄이기 위해서 다음과 같은 탐색 중단 로직을 넣어준다.
  • 한 곳에서라도 성능검사를 통과하지 못하는 경우 성능검사를 중단한다.
  • 약품 투입은 0회 ~ D회까지 진행할 수 있는데, 낮은 횟수부터 약품을 투입하다가 성능검사를 통과하는 경우 모든 탐색을 중단하고 답을 출력한다.

1. 약품을 투입할 막의 인덱스를 선정한다.
2. 선정된 막에는 A 혹은 B 약품을 투입할 수 있으므로 재귀적으로 약품을 투입할 수 있는 모든 조합을 찾는다.
3. 성능검사를 통과하는 경우 모든 탐색을 중단하고 재귀를 최대한 빨리 빠져나온다.

구현1

#include <iostream>
#include <memory.h>
#include <vector>
#define MAX_D 13
#define MAX_W 20

using namespace std;

int D, W, K;
int film[MAX_D][MAX_W];
int visited[MAX_D];
int ans = 0;
vector<int> cand; // 선택할 row index

void insertA(int idx) {
	for (int c = 0; c < W; c++) {
		film[idx][c] = 0;
	}
}

void insertB(int idx) {
	for (int c = 0; c < W; c++) {
		film[idx][c] = 1;
	}
}

bool testCells() {
	for (int c = 0; c < W; c++) {
		int numA = 0, numB = 0;
		bool flag = false;
		for (int r = 0; r < D; r++) {
			if (numA == K || numB == K) {
				flag = true;  
				break;
			}
			if (film[r][c] == 0) {
				numA++; numB = 0;
			}
			else if (film[r][c] == 1) {
				numB++; numA = 0;
			}
		}
		if (flag) continue;
		if (numA == K || numB == K) continue;
		return false;
	}
	return true;
}

bool insertAndTestProc(int node, int num) {
	if (node == num) {
		return testCells();
	}
	
	int cfilm[MAX_D][MAX_W];
	memcpy(cfilm, film, sizeof(cfilm));
	insertA(cand[node]);
	if (insertAndTestProc(node + 1, num)) return true;

	memcpy(film, cfilm, sizeof(film));
	insertB(cand[node]);
	if (insertAndTestProc(node + 1, num)) return true;
	memcpy(film, cfilm, sizeof(film)); // 원래대로 복구
	return false;
}

bool solutionProc(int v, int num) {
	if (cand.size() == num) {
		return insertAndTestProc(0, num);
	}

	for (int i = v; i < D; i++) {
		if (visited[i]) continue;
		visited[i] = true;
		cand.push_back(i);
		if (solutionProc(i + 1, num)) return true;
		cand.pop_back();
		visited[i] = false;
	}
	return false;
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> D >> W >> K;
		for (int r = 0; r < D; r++) {
			for (int c = 0; c < W; c++) {
				cin >> film[r][c];
			}
		}
		for (int num = 0; num <= D; num++) {
			cand.clear();
			memset(visited, false, sizeof(visited));
			if (solutionProc(0, num)) {
				cout << "#" << test_case << " " << num << "\n";
				break;
			}
		}
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

구현2

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>

#define MAX_D 13
#define MAX_W 20
#define CELL_A 0
#define CELL_B 1
using namespace std;

int D, W, K;
int cell[MAX_D][MAX_W];
vector<int> list;
vector<pair<int, int>> cand; // (row, color)
int visited[MAX_D];

void input()
{
	list.clear();
	cin >> D >> W >> K;
	for (int r = 0; r < D; r++) {
		list.push_back(r);
		for (int c = 0; c < W; c++) {
			cin >> cell[r][c];
		}
	}
}

bool isPassed()
{
	int tmpCell[MAX_D][MAX_W];
	memcpy(tmpCell, cell, sizeof(cell));
	for (auto ele : cand) {
		int row = ele.first;
		int color = ele.second;
		for (int c = 0; c < W; c++) {
			tmpCell[row][c] = color;
		}
	}

	// 디버깅
	/*printf("----------------\n");
	for (int r = 0; r < D; r++) {
		for (int c = 0; c < W; c++) {
			printf("%d ", tmpCell[r][c]);
		}
		printf("\n");
	}*/

	for (int c = 0; c < W; c++) {
		int refColor = tmpCell[0][c];
		int cnt = 1;
		for (int r = 1; r < D; r++) {
			if (refColor != tmpCell[r][c]) cnt = 1;
			else cnt++;
			refColor = tmpCell[r][c];
			if (cnt == K) break;
		}
		if (cnt == K) continue;
		return false;
	}
	return true;
}

bool dfs(int v, int cnt)
{
	if (cand.size() == cnt) {
		return isPassed();
	}

	for (int i = v; i < list.size(); i++) {
		if (visited[i]) continue;
		visited[i] = true;
		for (int color = 0; color < 2; color++) {
			cand.push_back(make_pair(list[i], color));
			if (dfs(i + 1, cnt)) return true;
			cand.pop_back();
		}
		visited[i] = false;
	}
	return false;
}

int solution()
{
	for (int cnt = 0; cnt <= D; cnt++) {
		memset(visited, false, sizeof(visited));
		cand.clear();
		if (dfs(0, cnt)) return cnt;
	}
	return  -1; // error
}

void test()
{
	cout << solution() << endl;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("sample_input.txt", "r", stdin);
	cin >> T;

	/*input();
	test();*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		printf("#%d %d\n", test_case, solution());
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}