BOJ 17136 : 색종이 붙이기 (A형 상시)

삼성 A형 전체 링크

www.acmicpc.net/workbook/view/2771 (상시 A형 문제집)

 

www.acmicpc.net/problem/17136

 

 

input에서 색종이 상태를 입력받고, 색종이의 개수 PAPER_COUNT에 저장해둔다.

그리고 각 색종이의 최대 개수인 5를 MAX_PAPER[1~5]에 저장한다.

#define MAX (10 + 10)

int MAP[MAX][MAX];
int PAPER_COUNT;
int MAX_PAPER[10];

void input()
{
	for (int r = 0; r < 10; r++)
	{
		for (int c = 0; c < 10; c++)
		{
			scanf("%d", &MAP[r][c]);
			PAPER_COUNT += MAP[r][c];
		}
	}

	for (int p = 1; p <= 5; p++) MAX_PAPER[p] = 5;
}

 

DFS로 완전 탐색을 하기 위해 아래의 3가지 함수를 만든다.

 

checkPaper는 (r, c) 좌표에 대해 색종이를 붙일 수 있는지 판단하는 함수이다.

붙일 수 있다면 addPaper로 색종이를 붙여 MAP을 size * size 만큼 0으로 만든다.

그리고 DFS 종료 후 복구하기 위해 revertPaper 함수로 MAP을 다시 1로 만든다.

int checkPaper(int sr, int sc, int size)
{
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			if (MAP[r][c] == 0) return 0;

	return true;
}

void addPaper(int sr, int sc, int size)
{
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			MAP[r][c] = 0;
}

void revertPaper(int sr, int sc, int size)
{
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			MAP[r][c] = 1;
}

 

 

DFS에의 Level(Depth)가 현재 색종이가 붙여진 횟수가 된다.

input에서 PAPER_COUNT에 색종이를 붙여야하는 크기를 저장해뒀으므로,

색종이를 붙일 때 마다 size * size만큼 뺀다. 

PAPER_COUNT가 0이 될 때 모든 색종이를 완벽하게 붙였으므로, DFS의 종료 조건이 된다.

 

색종이를 모두 붙일 때마다 MINANS를 갱신하고, 이미 MINANS보다 큰 L은 무시하도록 최적화한다.

int MINANS = 0x7fff0000;
void DFS(int L, int sr, int paperCount)
{
	if (L > MINANS) return; /* 최적화 */

	if (paperCount == 0)
	{
		if (L < MINANS) MINANS = L;
		return;
	}

	for (int r = sr; r < 10; r++)
	{
		for (int c = 0; c < 10; c++)
		{
			if (MAP[r][c] == 0) continue;

			for (int p = 1; p <= 5; p++)
			{
				if (MAX_PAPER[p] == 0) continue;
				if (r + p > 10 || c + p > 10) continue;

				if (checkPaper(r, c, p))
				{
					MAX_PAPER[p]--;
					addPaper(r, c, p);

					DFS(L + 1, r, paperCount - p * p);

					MAX_PAPER[p]++;
					revertPaper(r, c, p);
				}
			}

			return;
		}
	}
}

 

MAP을 전체 돌면서 좌표가 1인 위치부터 색종이를 붙이므로 0인 경우는 continue한다.

그리고 종이가 부족한 경우 MAX_PAPER[p] = 0인 경우도 continue한다.

좌표를 벗어나는 경우도 continue가 된다. 

 

색종이는 (r, c) 부터 (r + size - 1, c + size - 1) 까지 붙이기 때문에 좌표가 벗어나는 조건은 9가 아니라 10이 된다.

 

색종이를 붙일 수 있는 경우에 MAX_PAPER에서 paper의 개수를 감소하고, addPaper로 MAP을 0으로 바꾼다.

DFS 종료 후 복구한다.

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10 + 10)

int MAP[MAX][MAX];
int PAPER_COUNT;
int MAX_PAPER[10];

void input()
{
	for (int r = 0; r < 10; r++)
	{
		for (int c = 0; c < 10; c++)
		{
			scanf("%d", &MAP[r][c]);
			PAPER_COUNT += MAP[r][c];
		}
	}

	for (int p = 1; p <= 5; p++) MAX_PAPER[p] = 5;
}

void output()
{
	for (int r = 0; r < 10; r++)
	{
		for (int c = 0; c < 10; c++)
			printf("%d ", MAP[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

int checkPaper(int sr, int sc, int size)
{
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			if (MAP[r][c] == 0) return 0;

	return true;
}

void addPaper(int sr, int sc, int size)
{
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			MAP[r][c] = 0;
}

void revertPaper(int sr, int sc, int size)
{
	for (int r = sr; r < sr + size; r++)
		for (int c = sc; c < sc + size; c++)
			MAP[r][c] = 1;
}

int MINANS = 0x7fff0000;
void DFS(int L, int sr, int paperCount)
{
	if (L > MINANS) return;

	if (paperCount == 0)
	{
		if (L < MINANS) MINANS = L;
		return;
	}

	for (int r = sr; r < 10; r++)
	{
		for (int c = 0; c < 10; c++)
		{
			if (MAP[r][c] == 0) continue;

			for (int p = 1; p <= 5; p++)
			{
				if (MAX_PAPER[p] == 0) continue;
				if (r + p > 10 || c + p > 10) continue;

				if (checkPaper(r, c, p))
				{
					MAX_PAPER[p]--;
					addPaper(r, c, p);

					DFS(L + 1, r, paperCount - p * p);

					MAX_PAPER[p]++;
					revertPaper(r, c, p);
				}
			}

			return;
		}
	}
}

int main(void)
{
	input();

	DFS(0, 0, PAPER_COUNT);

	if (MINANS == 0x7fff0000) printf("-1\n");
	else printf("%d\n", MINANS);

	return 0;
}