[백준 17136] 색종이 붙이기

문제 링크 : 17136번: 색종이 붙이기 (acmicpc.net)

17136번: 색종이 붙이기

 

문제

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

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

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

출력

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

---

브루트 포스 및 백트래킹을 이용한 문제이다.

문제 접근법에 대해서 설명하자면 다음과 같다.

 

① 우선 (x, y) 위치에서 (x + n, y + n) 위치까지 색종이를 최대로 덮을 수 있는 사이즈를 Paper[x][y] = n + 1 이라고 한다.

Paper[x][y] 를 다음과 같이 구할 수 있다.

 

bool is_okay(int x, int y, int n) {
	if (x + n > 10 || y + n > 10) return false;
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (!Map[i][j]) return false;
		}
	}
	return true;
}

void set_paper() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (is_okay(i, j, 5)) Paper[i][j] = 5;
			else if (is_okay(i, j, 4)) Paper[i][j] = 4;
			else if (is_okay(i, j, 3)) Paper[i][j] = 3;
			else if (is_okay(i, j, 2)) Paper[i][j] = 2;
			else if (is_okay(i, j, 1)) Paper[i][j] = 1;
		}
	}
}

 

② (0, 0) 을 시작위치로 하여 (0, 0) => (0, 1) => (0, 2) => ... (0, 9) => (1, 0) => (1, 1) => ... => (9, 9) 순으로 접근하면서 해당 위치에  최대 사이즈 Paper[x][y] 부터 1 까지 덮어가도록 재귀적으로 구현했다.

우선 해당 사이즈 만큼 모든 위치에 1 이 존재할 경우 색종이를 덮을 수 있으며 그렇지 않은 경우 사이즈를 1씩 줄여가면서 다시 색종이를 덮을 수 있는지를 확인한다.

이를 구현한 코드는 다음과 같다.

 

int cur_paper = Paper[x][y];
int tmp[5][5];
while (cur_paper) {
	if (cnt[cur_paper - 1]) {
		bool op = true;
		for (int i = x; i < x + cur_paper; i++) {
			for (int j = y; j < y + cur_paper; j++) {
				if (!Map[i][j]) op = false;
            }
        }
        if (op) {
            for (int i = x; i < x + cur_paper; i++) {
                for (int j = y; j < y + cur_paper; j++) {
                    tmp[i - x][j - y] = Paper[i][j];
                    Paper[i][j] = Map[i][j] = 0;
                }
            }
            cnt[cur_paper - 1] -= 1;
            backtracking(x, y + cur_paper, cnt, total - cur_paper * cur_paper, how + 1);
            cnt[cur_paper - 1] += 1;
            for (int i = x; i < x + cur_paper; i++) {
                for (int j = y; j < y + cur_paper; j++) {
                    Paper[i][j] = tmp[i - x][j - y];
                    Map[i][j] = 1;
                }
            }
        }
    }
    cur_paper--;
}

 

③ 모든 색종이가 다 놓인 경우 즉, 각 칸에 적힌 수가 전부 0일 경우 값을 최소로 업데이트 한다.

이때 백트래킹 기법을 적용하여 색종이 갯수보다 같거나 같을 경우 아직도 색종이를 놓아야 할 경우에 대해서 return 을 해줘야 한다.

이에 대한 코드는 다음과 같다.

 

void backtracking(int x, int y, int cnt[], int total, int how) {
	if (total == 0) {
		result = min(result, how);
		return;
	}
	if (how >= result)
		return;
	if (y == 10) {
		if(x < 9) backtracking(x + 1, 0, cnt, total, how);
		return;
	}
	if (!Paper[x][y]) {
		if (x == 9 && y == 9) return;
		if (y == 9) backtracking(x + 1, 0, cnt, total, how);
		else backtracking(x, y + 1, cnt, total, how);
		return;
	}
    
    ...
}

 

④ 색종이를 최소로 놓을 수 있는 갯수가 업데이트 되지 않은 경우 -1 을 출력하도록 하고 그렇지 않을 경우 색종이를 최소로 놓을 수 있는 갯수를 출력하도록 한다.

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>

using namespace std;

int Map[10][10];
int Paper[10][10];
int N;
int result;

void input() {
	N = 0;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			scanf("%d", &Map[i][j]);
			if (Map[i][j]) N++;
		}
	}
}

bool is_okay(int x, int y, int n) {
	if (x + n > 10 || y + n > 10) return false;
	for (int i = x; i < x + n; i++) {
		for (int j = y; j < y + n; j++) {
			if (!Map[i][j]) return false;
		}
	}
	return true;
}

void set_paper() {
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (is_okay(i, j, 5)) Paper[i][j] = 5;
			else if (is_okay(i, j, 4)) Paper[i][j] = 4;
			else if (is_okay(i, j, 3)) Paper[i][j] = 3;
			else if (is_okay(i, j, 2)) Paper[i][j] = 2;
			else if (is_okay(i, j, 1)) Paper[i][j] = 1;
		}
	}
}

void backtracking(int x, int y, int cnt[], int total, int how) {
	if (total == 0) {
		result = min(result, how);
		return;
	}
	if (how >= result)
		return;
	if (y == 10) {
		if(x < 9) backtracking(x + 1, 0, cnt, total, how);
		return;
	}
	if (!Paper[x][y]) {
		if (x == 9 && y == 9) return;
		if (y == 9) backtracking(x + 1, 0, cnt, total, how);
		else backtracking(x, y + 1, cnt, total, how);
		return;
	}

	int cur_paper = Paper[x][y];
	int tmp[5][5];
	while (cur_paper) {
		if (cnt[cur_paper - 1]) {
			bool op = true;
			for (int i = x; i < x + cur_paper; i++) {
				for (int j = y; j < y + cur_paper; j++) {
					if (!Map[i][j]) op = false;
				}
			}
			if (op) {
				for (int i = x; i < x + cur_paper; i++) {
					for (int j = y; j < y + cur_paper; j++) {
						tmp[i - x][j - y] = Paper[i][j];
						Paper[i][j] = Map[i][j] = 0;
					}
				}
				cnt[cur_paper - 1] -= 1;
				backtracking(x, y + cur_paper, cnt, total - cur_paper * cur_paper, how + 1);
				cnt[cur_paper - 1] += 1;
				for (int i = x; i < x + cur_paper; i++) {
					for (int j = y; j < y + cur_paper; j++) {
						Paper[i][j] = tmp[i - x][j - y];
						Map[i][j] = 1;
					}
				}
			}
		}
		cur_paper--;
	}
}

void solution() {
	int cnt[5] = { 5,5,5,5,5 };
	
	result = 10000;
	set_paper();
	backtracking(0, 0, cnt, N, 0);
	if (result == 10000) printf("-1");
	else printf("%d", result);
}

int main()
{
	input();
	solution();

	return 0;
}