[백준 17136: 색종이 붙이기] (C++)

삼성 A형 기출 문제

https://www.acmicpc.net/workbook/view/2771

ㄴ색종이 붙이기

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

 

 

 

l 문제

 

1. 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

2. 색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다.

3.  1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

 

 

l 순서

 

1. 처음부터 1을 찾을 때까지 차례로 증가 ( 0, 0 ) ~ ( 10, 10 )

2. 1을 찾았다면 모든 크기의 색종이를 부착 시도한다. ( 5, 4 ,3, 2, 1 )

3. 색종이 부착 시도

4. 부착

5. 제거

 

 

l 입력

 

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

 

 

l 출력

 

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

 

 

l 풀이

 

DFS로 풀 수 있다.

색종이를 붙일 수 있는지 확인하는 함수 색종이 부착/제거 함수 DFS 함수 {   1. 종료 조건    ( ( 10, 10 )에 도달하면 종료  ) + 가지 치기   2. 색종이 부착 ( 5, 4, 3, 2, 1 모두 시도 )   3. 색종이 제거 }

색종이 부착 1이 등장하면 색종이 부착을 시도함 색종이 크기 size 는 5, 4, 3, 2, 1 차례로 모두 시도 ( x, y ) ~ ( x + size, y + size ) 범위가 모두 1이면 부착 가능

색종이 제거 매번 배열을 복사해서 진행해도 되지만 DFS라서 붙인 색종이를 제거하는 방식으로 전역 배열 하나로도 처리 가능

 

 

l  코드

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAX = 10;

int min_ans, total_cnt;
int paper_cnt[5] = { 0,0,0,0,0 };
int board[MAX][MAX];

bool can_attach_paper(int x, int y, int size)
{
	register int i, j;
	for (i = 0; i < size; ++i)
	{
		for (j = 0; j < size; ++j)
			if (!board[x + i][y + j])
				return false;
	}
	return true;
}

void update_paper(int x, int y, int size, bool is_attach)
{
	register int i, j;
	for (i = 0; i < size; ++i)
		for (j = 0; j < size; ++j)
				board[x + i][y + j] = is_attach;
}

void dfs(int x, int y, int attach_cnt)
{
	// 1. 1을 찾을 때까지 증가
	while (board[x][y] == 0)
	{
		if (++y >= MAX)
		{
			if (++x >= MAX)
			{
				min_ans = min(min_ans, attach_cnt);
				return;
			}
			y = 0;
		}
	}

	// 가지 치기
	if (min_ans <= attach_cnt)
		return;

	// 2. 모든 크기를 시도 (5,4,3,2,1)
	for (int s = 5; s > 0; --s)
	{
		// 범위 벗어남, 남은 종이 없음
		if (x + s > MAX || y + s > MAX || paper_cnt[s] == 5) continue;

		// 3. 색종이 부착 시도
		if (can_attach_paper(x, y, s))
		{
			// 4. 부착
			update_paper(x, y, s, 0);
			++paper_cnt[s]; 
			dfs(x, y, attach_cnt + 1); 

			// 5. 제거
			update_paper(x, y, s, 1);
			--paper_cnt[s];
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	min_ans = 987654321;
	register int i, j;
	for (i = 0; i < MAX; ++i)
	{
		for (j = 0; j < MAX; ++j)
		{
			cin >> board[i][j];
			if (board[i][j]) ++total_cnt;
		}
	}
	if (total_cnt == MAX * MAX)
	{
		cout << 4; 
        return 0;
	}

	dfs(0, 0, 0);
	if (min_ans == 987654321) min_ans = -1;
	cout << min_ans;
	return 0;
}