SWEA2112.md

보호 필름

https://swexpertacademy.com/ [2112]

개요

D(3<=D<=13)*W(1<=W<=20)의 맵이 0과 1로 구분되어 주어진다. 행을 선택하여 모두 0이나 1로 바꿀 수 있다고 하였을 때 모든 열에 대하여 연속된 0 또는 연속된 1이 K개 이상이 나오는 최소 행 선택개수를 구하는 문제

분석

D개의 행 중에 (K, K-1, K-2, K-3, ..., 1)개의 행을 선택하는 경우의 수*2(0과 1로 바꾸는 경우 2가지)가 모든 경우의 수이다. K개의 행을 선택한다면 연속된 행을 선택하여 모두 같은 숫자로 바꾸면 되므로 (K-1 ~ 1)개의 행만 선택하면 된다. 여기에 경우의 수마다 열의 개수 W만큼 0과 1로 바꾸어 주어야 하고 검사를 D*W 만큼 해야하므로 최악의 경우 (13C6+a)*2*13*13*20 = 1060만 + b 이 된다.

경험상 모든 테스트케이스가 최악의 경우라도 아슬아슬하게 시간제한 내에 풀 수있다. BFS의 형식을 빌려 변경이 적을 때를 우선적으로 검사하여 이후 검사를 하지 않는다면 안정적인 시간으로 풀 수 있다.

알고리즘

1. 맵을 미리 mapb에 복사해둔다.
2. answer을 -1로 초기화한다.
3. 변경하는 행의 개수를 step으로 두어 step을 1~k-1까지 반복한다.
   1. dfs를 돌린다.
      1. answer이 -1 이 아닌 경우는 최소 step을 찾은 경우이므로 무조건 return시킨다.
      2. 모든 열에 대해 K개 이상의 연속된 0 또는 1이 있는 지 검사한다. (chk)
         1. 검사를 충족하면 answer=step
      3. 전에 선택한 행의 다음행~마지막 행 중에 행을 하나 선택한다.
      4. 0이나 1로 갱신한다.
      5. dfs
      6. mapb를 이용하여 선택했던 행을 원상복귀한다.
4. 만약 answer이 -1이라면 0~k-1 번에 조건을 만족하는 경우가 없는 것이므로 answer=k
5. answer 출력

소스

#include <stdio.h>

int answer, step, d, w, k, map[15][25], mapb[15][25];

void chk()
{
	int i, j, cnt, flag;
	for (i = 1; i <= w; i++)
	{
		cnt = 1;
		flag = 0;
		for (j = 1; j < d; j++)
		{
			if (map[j][i] == map[j + 1][i]) ++cnt;
			else cnt = 1;

			if (cnt == k)
			{
				flag = 1;
				break;
			}
		}
		if (flag == 0) return;
	}
	answer = step;
}
void cha(int h, int v)
{
	int i;
	for (i = 1; i <= w; i++) map[h][i] = v;
}
void recha(int h)
{
	int i;
	for (i = 1; i <= w; i++) map[h][i] = mapb[h][i];
}

void dfs(int st, int se)
{
	int i, j;
	if (answer != -1) return;
	else if (step == st - 1)
	{
		chk();
		return;
	}

	for (i = se+1; i <= d; i++)
	{
		for (j = 0; j < 2; j++)
		{
			cha(i, j);
			dfs(st + 1, i);
		}
		recha(i);
	}

}

int main()
{
	int t, i, j, ii;
	scanf("%d", &t);
	for (i = 1; i <= t; i++)
	{
		scanf("%d%d%d", &d, &w, &k);
		for (j = 1; j <= d; j++)
		{
			for (ii = 1; ii <= w; ii++)
			{
				scanf("%d", &map[j][ii]);
				mapb[j][ii] = map[j][ii];
			}
		}
		step = 0;
		answer = -1;

		chk();
		for (j = 1; j < k; j++)
		{
			step = j;
			dfs(1, 0);
		}
		if (answer == -1) answer = k;

		printf("#%d %d\n", i, answer);
	}
}