[SWEA 2112] 보호 필름

https://swexpertacademy.com/main/talk/solvingClub/problemView.do

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <algorithm>
int T;
int R, C, K;
int board[13 + 2][20 + 2];
int ans = 0x7fffffff;

void input()
{
	//init
	memset(board, 0, sizeof(board));
	ans = 0x7fffffff;

	scanf("%d %d %d", &R, &C, &K);
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			scanf("%d", &board[r][c]);
		}
	}
}



bool chk_pass()
{
	for (int c = 0; c < C; c++) {
		int curr_type = board[0][c];
		int curr_cnt = 1;
		int pass = false;
		for (int r = 1; r < R; r++) {
			if (curr_type == board[r][c]) {
				curr_cnt++;
				if (curr_cnt >= K) {
					pass = true;
					break;
				}
			}
			else {
				curr_type = board[r][c];
				curr_cnt = 1;
			}
		}
		if (pass == false) return false;
	}
	return true;
}


void DFS(int row, int cnt)
{

	//가지치기 조건 // 이거 없으면 실행시간 5배 차이남
	if (ans < cnt) return;

	if (K == 1) { 	// 엣지케이스 생각
		ans = cnt;
		return;
	}
	if (chk_pass()) {
		if (ans > cnt) ans = cnt;
		return;
	}
	if (row > R - 1) return;

	// backup
	int tmp[20 + 2];
	memcpy(tmp, board[row], sizeof(tmp));

	// 아무것도 투입하지 않음 
	DFS(row + 1, cnt);

	// 약품 A 투입
	std::fill(board[row], board[row] + C, 0);
	DFS(row + 1, cnt + 1);
	memcpy(board[row], tmp, sizeof(tmp));

	// 약품 B 투입
	std::fill(board[row], board[row] + C, 1);
	DFS(row + 1, cnt + 1);
	memcpy(board[row], tmp, sizeof(tmp));
}


int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		input();
		DFS(0, 0);
		printf("#%d %d\n", t, ans);
	}
	return 0;
}

엣지케이스 주의하자... 

---

이전 코드 및 코멘트..

#include <cstdio>
#include <algorithm>
#include <cstring>
int T;
int D, W, K;	// 행 열 합격컷
int Fig[13 + 2][20 + 2];
int Cpy[13 + 2][20 + 2];
int ans = 0x7fffffff;



void init()
{
	std::fill(&Fig[0][0], &Fig[0][0] + sizeof(Fig) / sizeof(int), 0);
	std::fill(&Cpy[0][0], &Cpy[0][0] + sizeof(Cpy) / sizeof(int), 0);
	ans = 0x7fffffff;
}


void input()
{
	scanf("%d %d %d", &D, &W, &K);
	for (int i = 0; i < D; i++) {
		for (int j = 0; j < W; j++) {
			scanf("%d", &Fig[i][j]);
			Cpy[i][j] = Fig[i][j];
		}
	}
}


// 여기서 for 루프 세 번 돌리면 안됨 .. 시간 초과 난다.. 
bool chk_pass()
{
	for (int j = 0; j < W; j++) {
		int comp = Cpy[0][j], chk = 1;	// 비교할 것 : Cpy배열의 j번째 열의 첫번째 행 원소
		for (int i = 1; i < D; i++) {
			if (comp == Cpy[i][j]) {
				chk++;
				if (chk == K) break;
			}
			else {
				comp = Cpy[i][j], chk = 1;
			}
		}
		if (chk != K) return false;		// 해당 열에 대하여 chk 개수가 K보다 작으면 합격 컷 이하임 
	}
	return true;	// 만약에 루프 다 돌면 모든 열이 합격 컷 이상임
}


void DFS(int n, int cnt)
{
	if (ans <= cnt) return;

	if (chk_pass()) {
		ans = cnt;
		return;
	}

	if (n == D) return;

	// 아무것도 안함 
	DFS(n + 1, cnt);

	// A약품으로 처리
	std::fill(Cpy[n], Cpy[n] + W, 0);
	DFS(n + 1, cnt + 1);

	// B약품으로 처리 
	std::fill(Cpy[n], Cpy[n] + W, 1);
	DFS(n + 1, cnt + 1);

	// 원복 
	std::copy(Fig[n], Fig[n] + W, Cpy[n]);
}



int main()
{
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		init();
		input();
		DFS(0, 0);	// 몇번째 행의 상태인지, 약품 몇 회 사용했는지 
		printf("#%d %d\n", t + 1, ans);
	}
	return 0;
}

시간초과로 개고생 했던 문제이다. 

사실 접근부터 글러먹었기 때문에 별로 타격은 없다... 그냥 또 생각 안한 내가 바보인것.. 

 

 

문제에서 DFS를 사용할 때는 앞으로 다음의 사항들을 생각해야 겠다.

1. 인자로 무엇을 넘길 것인가 ? 

2. 모든 경우의 수가 시도해볼 법한 경우의 수 인가?

3. 무엇에 대한 경우의 수를 따질 것인가 ? 내가 탐색하고자 하는 상태가 무엇인가 ? 

 

 

사실 처음에는 중복 조합으로 몇 개의 행에 약물 투입할 것인지 => 중복 순열로 해당 행에 A약물 투입할 것인지 B약물 투입할 것인지 => 투입 후 모든 열이 합격 컷 K를 통과하는지의 순서로 구현했다. 

당연히 시간초과 났고 테케는 26 / 50 정도 맞은듯 ... ㅋㅋ... 

 

 

이 문제에서 탐색하고자 하는 것은 약물의 최소 투입 횟수이다.

한편 각 열의 합격 컷 K를 확인할 때 약물의 종류도 중요하다. 

따라서 한 행에 대하여 정의할 수 있는 상태는 3가지 이다. 

1. 아무 행동도 하지 않든지 

2. A번 약물을 투입하든지

3. B번 약물을 투입하든지 

이렇게 각 행에 대한 상태를 3가지로 정의하고, 최대 13개의 행에 대하여 DFS를 돌리면 연산량은 대략 3^13이다. 

 

 

 또 한가지 중요한 사실은, 행의 상태를 바꿀 때 맵 전체를 복사할 필요는 없다는 것이다. 

나는 처음에 상태 발전을 위해 모든 맵을 memcpy로 복사했는데, 이럴 필요 없이 행 단위로 약물의 종류에 따라 채워주고 원래 맵을 사용하여 다시 원복해주면 된다. (algorithm의 fill & copy 함수)

 

 

마지막으로 쓸데없이 돌리는 루프는 연산량을 가중시킨다. 

나는 각 열마다 합격 컷 K를 통과하는지를 3번의 루프를 사용해서 확인했는데, 이것도 시간초과를 유발하는 요인 중 하나였다. 이 방법 보다는 각 열을 항상 행의 0번째 인덱스부터 탐색하므로 비교할 초기값 comp 를 Cpy[0][j] 로 지정하고, 루프를 돌면서 만약 다음 행이 comp와 같다면 chk++한다(K까지 되는지 확인하기 위해). 만약 다른 값이 나온다면 비교할 초기값 comp를 Cpy[i][j]로 갱신하고, chk변수도 따라서 0으로 갱신해준다. 

이렇게 하면 (i, j)마다 이루어졌던 K번의 연산을 생략할 수 있다.