Baekjoon 17136 색종이 붙이기

Link https://www.acmicpc.net/problem/17136

소스결과 1988 KB / 36 ms

언어 C++ 17

출처 Baekjoon

분류 브루트 포스

 

설명

10 x 10 의 판에 1 이 적힌 부분을 덮기 위해 필요한 색종이의 수를 구하여라.

 

삽질에 삽질에 삽질을 했던 문제. 타임아웃 문제를 해결해야 했던 문제도, 그리디로 처리해 오답이 나온 경우도 있었다.

타임아웃의 경우는 한 위치에서 5x5 색종이가 놓는게 가능하다 할 때 이 위치는 4,3,2,1 이 가능하기때문에 모든 경우에 다 대입하는 방법이었는데 시간도 오래 걸릴 뿐 더러, 굳이 할 필요가 없는 문제였다.

그리디로 처리한 경우는 예제중 한 경우도 통과 못했었다.

정답은 타임아웃 경우를 조금 수정한 방법이었는데. 색종이를 놓을 수 있는 가장 처음 위치(0,0)에 가장 가까운 위치를 기준으로 놓을 수 있는 모든 경우를 대입하여 처리 하는 방법이었다.

 

알고리즘

1. 색종이를 놓을 첫 위치를 탐색한다.

2. 첫 위치에 대해서 5x5가 가능한 경우 1x1까지 탐색한다.

3. 위치가 결정된 뒤, 색종이를 놓은게 처리가 되면, 다음 위치를 탐색하고 이동한다.

 3-1. 색종이는 각각 5장이 최대이므로, 남은 색종이가 없으면 놓지 않는다.

4. 다음 위치도 2번과 같은 알고리즘으로 처리한다.

5. 결과값을 출력한다.

 

소스코드

#include <iostream>

using namespace std;

const short	BOARD_MAX = 10;

struct Point {
	short x;
	short y;

	Point() { };
	Point(short x, short y) : x(x), y(y) {}
};

bool board[BOARD_MAX][BOARD_MAX];
int res = -1;

bool locationAble(bool board[BOARD_MAX][BOARD_MAX], Point p, int size)
{
	bool res = false;

	if (p.x + size <= BOARD_MAX && p.y + size <= BOARD_MAX)
	{
		res = true;
		for (int i = p.x; i < p.x + size; i++)
			for (int j = p.y; j < p.y + size; j++)
				if (!board[i][j])
					return false;
	}

	return res;
}

bool isClear(bool board[BOARD_MAX][BOARD_MAX])
{
	for (int i = 0; i < BOARD_MAX; i++)
		for (int j = 0; j < BOARD_MAX; j++)
			if (board[i][j])
				return false;
	return true;
}

Point nextPoint(bool board[BOARD_MAX][BOARD_MAX])
{
	Point res(BOARD_MAX, BOARD_MAX);
	for (int i = 0; i < BOARD_MAX; i++) {
		for (int j = 0; j < BOARD_MAX; j++)
		{
			if (board[i][j]) {
				res.x = i;
				res.y = j;
				break;
			}
		}
		if (res.x != BOARD_MAX && res.y != BOARD_MAX)
			break;
	}

	return res;
}

void solution(bool board[BOARD_MAX][BOARD_MAX], int paper[5], Point p, int cnt)
{
	if (p.x == BOARD_MAX && p.y == BOARD_MAX)
	{
		if (res == -1)
			res = cnt;
		else
			if (res > cnt)
				res = cnt;
	}
	else
	{
		for (int s = 5; s > 0; s--)
		{
			if (paper[s - 1] > 0)
			{
				if (locationAble(board, p, s))
				{
					for (int px = p.x; px < p.x + s; px++)
						for (int py = p.y; py < p.y + s; py++)
							board[px][py] = false;

					Point next = nextPoint(board);

					paper[s - 1]--;

					solution(board, paper, next, cnt + 1);

					paper[s - 1]++;

					for (int px = p.x; px < p.x + s; px++)
						for (int py = p.y; py < p.y + s; py++)
							board[px][py] = true;
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < BOARD_MAX; i++)
		for (int j = 0; j < BOARD_MAX; j++)
			cin >> board[i][j];

	int paper[] = { 5, 5, 5, 5, 5 };

	solution(board, paper, nextPoint(board), 0);

	cout << res;

	return 0;
}