boj,백준) 17136 색종이 붙이기 (C / C++)

1. 문제 링크

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

17136번: 색종이 붙이기

2. 문제 개요

 1이 적힌 칸을 모두 색종이로 덮는데 필요한 최소 개수를 구하는 문제.

 

3. 문제 힌트!!

 Greedy + DFS 문제라고 생각해보기.

Greedy -> 1x1부터 덮지 않고 5x5부터 즉, 최대한 큰 크기부터 덮어보기.

DFS -> backtracking

 

4. 문제 풀이

 

(1) 맵을 왼쪽위부터 오른쪽 밑으로 스캔한다.

(2) '1'을 발견하면 5x5 size의 색종이부터 놓을 수 있는지 검사한다. (5x5 -> 4x4... -> 1x1)

(3) 놓을 수 있다면 놓고 다시 스캔한다.

(4) 1종류의 색종이를 5장이상 사용했거나, 맨 끝(NxN)에 도착했지만 모든 1을 덮지 못하였을 경우 backtracking을 사용하여 돌아간다.

 

위의 내용을 코드로 잘 옮길 수 있느냐가 문제다.

 

5. 코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int map[10][10];
int papernum = 0;
int ret = 0x7fffffff;
int use[] = { 0,5,5,5,5,5 };
bool icanput(int y, int x, int size)
{
	if (y + size > 10 || x + size > 10 || use[size] == 0)	return false;

	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			if (map[i][j] == 0)
				return false;
	return true;
}
void putpaper(int y, int x, int size)
{
	use[size]--;
	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			map[i][j] = 0;
	papernum -= size*size;
	return;
}
void cleanpaper(int y, int x, int size)
{
	use[size]++;
	for (int i = y; i < y + size; i++)
		for (int j = x; j < x + size; j++)
			map[i][j] = 1;
	papernum += size*size;
	return;
}
void dfs(int depth, int y, int x)
{
	if (papernum == 0)
	{
		ret = min(ret, depth);
		
		return;
	}
	
	for (int i = y; i < 10; i++) {
		for (int j = x; j < 10; j++)
		{
			if (map[i][j] == 1)
			{
				for (int k = 5; k >= 1; k--)
				{
					if (icanput(i, j, k))
					{
						putpaper(i, j, k);
						dfs(depth + 1, i, j + k);
						cleanpaper(i, j, k);
					}
				}
				return;
			}
		}
		x = 0;
	}
}
int main(void)
{
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++){
			scanf("%d", &map[i][j]);
			if(map[i][j] == 1)
				papernum++;
		}

	dfs(0,0,0);
	if (ret == 0x7fffffff)
		printf("-1");
	else
		printf("%d", ret);
	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~