백준 17136 : 색종이 붙이기 C++

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

후기

1. 처음에 큰 색종이부터 대입시키면서 했는데 안되길래

0 0 0 0 0 0 0 0 0 0

0 0 1 1 1 1 1 1 0 0

0 0 1 1 1 1 1 1 0 0

0 0 1 1 1 1 1 1 0 0

0 0 1 1 1 1 1 1 0 0

0 0 1 1 1 1 1 1 0 0

0 0 1 1 1 1 1 1 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

요거 대입하니까 오답나와서 구글링 해서 다시 풀었다.

 

2. DFS로 풀었고 생각보다 어렵지 않았다.

3. 여기서 등호 붙인거를 못찾고 30분 해맨건 안비밀 ㅠㅠ

    if (r + i > 10 || c + i > 10)//지도 벗어나면 스킵!
        continue;

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int map[11][11];
int answer = 987654321;
int paper[6] = { 0, };

bool possible(int r, int c, int size)
{
	for(int i=0;i<size;i++)
		for (int j = 0; j < size; j++)
		{
			if (map[r + i][c + j] == 0)
				return false;
		}

	return true;
}


void dfs(int r, int c, int cnt)
{
	while (map[r][c] == 0)//1을 찾아야됨!!!
	{
		c++;
		if (c >= 10)
		{
			r++;
			if (r >= 10)//맨끝 도착!!
			{
				answer = min(answer, cnt);
				return;
			}
			c = 0;
		}
	}
	if (cnt >= answer)
		return;

	for (int i = 5; i >= 1; i--)//종이 젤 큰거부터 시도!
	{
		if (r + i > 10 || c + i > 10)//지도 벗어나면 스킵!
			continue;
		if (paper[i] >= 5)//종이는 최대 5개!
			continue;

		if (possible(r, c, i))//종이 붙이기 가능이면!
		{
			paper[i]++;
			for(int a=0;a<i;a++)
				for (int b = 0; b < i; b++)
				{
					map[r + a][c + b] = 0;
				}

			dfs(r, c, cnt + 1);

			paper[i]--;
			for (int a = 0; a < i; a++)
				for (int b = 0; b < i; b++)
				{
					map[r + a][c + b] = 1;
				}
		}

	}

}

int main()
{
	for(int i=0;i<10;i++)
		for (int j = 0; j < 10; j++)
		{
			cin >> map[i][j];
		}

	dfs(0, 0, 0);
	if (answer == 987654321)
		answer = -1;

	cout << answer << endl;
	return 0;
}