[BOJ] 17136 색종이 붙이기

Link

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

Note

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

삽질에 삽질에 삽질을 했던 문제. 타임아웃 문제를 해결해야 했던 문제도, 그리디로 처리해 오답이 나온 경우도 있었다.
타임아웃의 경우는 한 위치에서 5x5 색종이가 놓는게 가능하다 할 때 이 위치는 4,3,2,1 이 가능하기때문에 모든 경우에 다 대입하는 방법이었는데 시간도 오래 걸릴 뿐 더러, 굳이 할 필요가 없는 문제였다.
그리디로 처리한 경우는 예제중 한 경우도 통과 못했었다.
정답은 타임아웃 경우를 조금 수정한 방법이었는데. 색종이를 놓을 수 있는 가장 처음 위치(0,0)에 가장 가까운 위치를 기준으로 놓을 수 있는 모든 경우를 대입하여 처리 하는 방법이었다.

알고리즘

1. 색종이를 놓을 첫 위치를 탐색한다.
2. 첫 위치에 대해서 5x5가 가능한 경우 1x1까지 탐색한다.
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;
}

2019-06-02 19:43:46에 Tistory에서 작성되었습니다.