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

url: https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

풀이 핵심

1. Back Tracking, Bruth Force 문제 (완전 탐색)

D_C_x (Combination, D개의 행 중 x개 선택)

2^x (x개가 A 또는 B로 약물 투입하는 경우)

D*W (W개의 열에서 연속된 수 찾는 경우)

 

D_C_x * 2^x * D * W ~= 대략 4억 (완전 탐색 가능)

 

2. struct Film을 만들고 성능을 검사하는 (check) 함수와 약물 투입 함수 (dosage) 를 만든다.

- check 함수

• 열마다 검사 해준다.
• 열마다 검사를 통과했는지 확인할 수 있는 test[MAXW] 배열을 만든다.
• 조금 더 빠르게 검사를 하기 위해 (cnt + D - 1 - r) 이 K 보다 작으면 검사를 종료한다.
• 열 하나라도 검사를 통과하지 못하면 바로 검사를 종료한다.
• 검사를 모두 통과하면 true 그렇지 못하면 false를 return 한다.

 

- dosage 함수

• target (열), type (A or B) 를 전달받는다 (전달인자).
• 복용을 했으므로 doses 변수를 하나 증가시킨다.
• 중복 투약을 방지하기 위해 is_dosage[target]을 true로 만든다.
• target 열을 모두 type (A or B)로 만든다.

 

3. 재귀 함수 형태의 solve 함수를 만든다.

• 전달 인자는 Film type의 cur과 target (열)을 받는다.
• 만약 현재 투약 횟수가 ans 보다 크거나 같으면 return 한다. (투약 횟 수 최소이어야 하므로)
• target이 D가 되면 검사를 하고 검사를 통과하면 투약 횟수와 ans를 비교하여 작을 경우 저장한다.
• 세 가지 경우로 solve 함수가 재 실행될 수 있도록 한다.
• 1) 현재 target 열에 투약하지 않음
• 2) 현재 target 열에 A 타입 투약
• 3) 현재 target 열에 B 타입 투약

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#define MAXD    13
#define MAXW    20
// 특성 A: 0, 특성 B: 1

int T, D, W, K, ans;

struct Film {
	int map[MAXD][MAXW];
	int doses; // 투약 횟 수
	bool is_dosage[MAXD];

	void init() {
		ans = K, doses = 0;
		for (int c = 0; c < W; c++) {
			is_dosage[c] = false;
		}
	}

	bool check() { // 검사
		bool test[MAXW] = { 0, };
		for (int c = 0; c < W; c++) {
			int flag = map[0][c], cnt = 1;
			for (int r = 1; r < D; r++) {
				if (map[r][c] == flag) {
					cnt++;
				}
				else {
					flag = map[r][c];
					cnt = 1;
					if ((cnt + D - 1 - r) < K) {
						break;
					}
				}
				if (cnt == K) {
					test[c] = true;
					break;
				}
			}
			if (!test[c]) {
				return false;
			}
		}
		return true;
	}

	void dosage(int target, int type) { // 투약
		doses++;
		is_dosage[target] = true;
		for (int c = 0; c < W; c++) {
			map[target][c] = type;
		}
	}
};

Film film;

void solve(Film cur, int target) {
	if (cur.doses >= ans) {
		return;
	}
	if (target == D) {
		if (cur.check()) {
			int candi = cur.doses;
			if (candi < ans) {
				ans = candi;
			}
		}
		return;
	}
	solve(cur, target + 1);
	if (!cur.is_dosage[target]) {
		for (int type = 0; type < 2; type++) {
			Film next = cur;
			next.dosage(target, type);
			solve(next, target + 1);
		}
	}
}

int main() {
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		scanf("%d %d %d", &D, &W, &K);
		for (int r = 0; r < D; r++) {
			for (int c = 0; c < W; c++) {
				scanf("%d", &film.map[r][c]);
			}
		}
		if (K == 1 || film.check()) { // K가 1이면 투약 하지 않아도 무조건 검사 통과
			ans = 0;
		}
		else {
			film.init(); // 초기화
			solve(film, 0);
		}
		printf("#%d %d\n", tc, ans);
	}
	return 0;
}