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

[문제]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

SW Expert Academy

[풀이과정]

사용언어 : c++

 

1. 완전탐색으로 풀었다.

 

2. 모든 W에 K갯수만큼의 세로의 셀이 존재하면 합격 기준이 된다. 따라서 K개의 약품을 투입하면 통과됨으로 시작 Answer값은 K로 시작했다.

 

3. 세로라인을 체크하는 checkMap함수를 만들었다. 세로라인에 셀 중 같은 값이 연속적으로 K개가 존재하는지 판단하는 함수이다.

 

4. 이제 약품을 1, 0으로 만들어주면서 모든 경우의 수를 찾아 최솟값을 구하면 된다.

 

5. checkLine함수를 통해 해당 셀에 약품을 투여할지를 판단한다.

이미 해당 셀 모두 1값이라면 1번 약품을 투여 할 필요는 없기 때문이다.

 

6. 구해진 Answer값보다 더 큰 탐색은 종료시켜주고, 최대값을 넘어선 탐색 또 한 종료시켜줬다.

 

소스코드

#include<stdio.h>
#include<string.h>

int map[13][20];
int visited[13];
int T, D, W, K;
int answer = 13;
bool checkMap()
{
	//세로라인 검사
	int prev, count, flag;
	for (int i = 0; i < W; i++) {
		prev = map[0][i];
		count = 1;
		flag = 1;
		for (int j = 1; j < D; j++) {
			if (prev == map[j][i]) {
				count++;
			}
			else {
				prev = map[j][i];
				count = 1;
			}

			if (count >= K) {
				flag = 0;
				break;
			}
		}
		if (flag) {
			return false;
		}
	}
	return true;
}
bool lineCheck(int y, int num) {
	for (int i = 0; i < D; i++) {
		if (map[y][i] == num) continue;
		return true;
	}
	return false;
}
void solution(int begin, int count)
{
	if (count >= K) {
		return;
	}
	if (answer <= count) {
		return;
	}
	if (checkMap()) {
		if (answer > count) {
			answer = count;
		}
		return;
	}

	int cpymap[13][20] = { 0, };
	memcpy(cpymap, map, sizeof(map));
	for (int i = begin; i < D; i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			if (lineCheck(i, 1)) {
				for (int j = 0; j < W; j++) {
					map[i][j] = 1;
				}
				solution(i + 1, count + 1);
			}
			if (lineCheck(i, 0)) {
				for (int j = 0; j < W; j++) {
					map[i][j] = 0;
				}
				solution(i + 1, count + 1);
			}
			memcpy(map, cpymap, sizeof(map));
			visited[i] = 0;
		}
	}
}

int main()
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++) {
		memset(map, 0, sizeof(map));
		memset(visited, 0, sizeof(visited));
		scanf("%d %d %d", &D, &W, &K);
		for (int i = 0; i < D; i++) {
			for (int j = 0; j < W; j++) {
				scanf("%d", &map[i][j]);
			}
		}
		answer = K;
		solution(0, 0);
		printf("#%d %d\n",tc, answer);
	}
}

 

[결과]