SWEA 2112 : 보호 필름 (모의 SW 역량테스트)

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

보호 필름

 

이후 설명 및 입/출력은 링크 참고

문제에서 요구한 대로 약품을 투입한다.

이 때, DFS에서 매번 MAP을 copy하는 비용을 낮추기 위해 약간의 테크닉을 사용할 수 있다.

특성 A가 0, B가 1이므로, MAP[1]에는 0을, MAP[2]에는 1을 저장해둔다.

int MAP[3][MAX][MAX];
int list[MAX];

void input()
{
	scanf("%d %d %d", &D, &W, &K);

	for (int r = 1; r <= D; r++)
		for (int c = 1; c <= W; c++)
			scanf("%d", &MAP[0][r][c]);
}

int main(void)
{
	/* MAP[2]에는 모두 B약품 1 저장 */
	for (int r = 1; r <= MAX - 1; r++)
		for (int c = 1; c <= MAX - 1; c++) MAP[2][r][c] = 1;
        
	...
}

 

이렇게 해두고, list에는 약품을 투입하지 않을지, A를 투입할지, B를 투입할지를 DFS로 만들면 된다.

따라서 성능검사를 통과하는지 check하는 함수는 아래처럼 만들 수 있다.

list가 모두 0이라면, list[r]은 모두 0이기 때문에 MAP[0] → 입력값을 그대로 보고 성능검사를 한다.

list[r]이 1이라면 MAP[1], 즉 A 약품만 보게 되고, list[r]이 2 라면 B 약품만 보게 된다.

/* 1 = A, 2 = B */
int list[MAX];

int check(int col)
{
	int cnt, tmp;

	cnt = 1;
	tmp = MAP[list[1]][1][col];
	for (int r = 2; r <= D; r++)
	{
		if (cnt == K) return 1;
		if (tmp == MAP[list[r]][r][col]) cnt++;
		else
		{
			tmp = MAP[list[r]][r][col];
			cnt = 1;
		}
	}

	if (cnt == K) return 1;
	return 0;
}

int allCheck()
{
	for (int c = 1; c <= W; c++)
		if (check(c) == 0) return 0;

	return 1;
}

 

DFS는 약품을 투입하지 않는 경우, A를 투입하는 경우, B를 투입하는 경우로 만들면 된다.

약품을 투입하지 않는 경우는 cnt를 증가시킬 필요가 없다.

또한 이미 답이 나온 경우보다 cnt가 커진다면 더 이상 DFS를 진행할 필요가 없다.

int MINANS = 0x7fff0000;
void DFS(int L, int cnt)
{
	if (MINANS <= cnt) return;

	if (L > D)
	{
		if (allCheck())
		{
			if (cnt < MINANS) MINANS = cnt;
		}

		return;
	}

	list[L] = 0;
	DFS(L + 1, cnt);

	list[L] = 1;
	DFS(L + 1, cnt + 1);

	list[L] = 2;
	DFS(L + 1, cnt + 1);
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (25 + 5)

int T, D, W, K;
int MAP[3][MAX][MAX];

void input()
{
	scanf("%d %d %d", &D, &W, &K);

	for (int r = 1; r <= D; r++)
		for (int c = 1; c <= W; c++)
			scanf("%d", &MAP[0][r][c]);
}

/* 1 = A, 2 = B */
int list[MAX];

int check(int col)
{
	int cnt, tmp;

	cnt = 1;
	tmp = MAP[list[1]][1][col];
	for (int r = 2; r <= D; r++)
	{
		if (cnt == K) return 1;
		if (tmp == MAP[list[r]][r][col]) cnt++;
		else
		{
			tmp = MAP[list[r]][r][col];
			cnt = 1;
		}
	}

	if (cnt == K) return 1;
	return 0;
}

int allCheck()
{
	for (int c = 1; c <= W; c++)
		if (check(c) == 0) return 0;

	return 1;
}

int MINANS = 0x7fff0000;
void DFS(int L, int cnt)
{
	if (MINANS <= cnt) return;

	if (L > D)
	{
		if (allCheck())
		{
			if (cnt < MINANS) MINANS = cnt;
		}

		return;
	}

	list[L] = 0;
	DFS(L + 1, cnt);

	list[L] = 1;
	DFS(L + 1, cnt + 1);

	list[L] = 2;
	DFS(L + 1, cnt + 1);
}

int main(void)
{
	/* MAP[2]에는 모두 B약품 1 저장 */
	for (int r = 1; r <= MAX - 1; r++)
		for (int c = 1; c <= MAX - 1; c++) MAP[2][r][c] = 1;

	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		MINANS = 0x7fff0000;

		DFS(1, 0);

		printf("#%d %d\n", tc, MINANS);
	}

	return 0;
}