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

문제 링크

---

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

접근 방법

---

 DFS로 접근하여 풀 수 있는 문제였으나 시간 초과를 해결하는 과정이 관건이었던 문제였다.

전체 공간인 map[10][10]을 탐색하면서 색종이를 붙여야 되는 공간이 있다면 큰 색종이 부터 시작하여 붙일 수 있는지에 대한 여부를 확인하고 색종이를 붙인다. 완전탐색으로 가장 적은 색종이를 사용하는 경우의 값을 구하면 된다. 

 

 시간초과를 해결하는 방법을 떠올리기가 쉽지가 않았는데 핵심은 현재 공간에 어떤 색종이도 만족하지 않는다면 그 다음 과정에서 이러한 공간을 어차피 만족시킬 수 없다는 것이다. 즉 현재 공간을 만족시킬 수 없다면 다음 과정으로 진행을 시키지 않는 것이 시간초과를 해결하는 핵심이었다.

int solve(int x, int y, int cnt) {

	if (complete()) 
		return cnt;
	if (mincnt <= cnt)
		return mincnt;

	for (int i = x; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 1) {
				for (int size = 5; size >= 1; size--) {
					if (inRange(i, j, size)) {
						if (check_map(i, j, size) && cntPerSize[size] > 0) {
							cntPerSize[size]--;
							update_map(i, j, size, 0);							
							mincnt = min(solve(i, j, cnt + 1), mincnt);
							cntPerSize[size]++;
							update_map(i, j, size, 1);
						}
					}
				}
				return mincnt; // !!!중요: 위의 과정에서 만족하지 않는다면 return시킴
			}
		}
	}

	return mincnt;
}

 

소스 코드

---

#include <iostream>
#include <algorithm>

using namespace std;

int map[10][10];
int cntPerSize[6] = { 0,5,5,5,5,5 };
int mincnt = 99999;

bool inRange(int x, int y, int size) {
	return (x + size - 1 < 10 && y + size - 1 < 10) ? true : false;
}

void update_map(int x, int y, int size, int action) {
	for (int i = x; i < x + size; i++)
		for (int j = y; j < y + size; j++)
			map[i][j] = action;
}

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

bool complete() {
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < 10; j++)
			if (map[i][j] == 1)
				return false;
	return true;
}

int solve(int x, int y, int cnt) {

	if (complete()) 
		return cnt;
	if (mincnt <= cnt)
		return mincnt;

	for (int i = x; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			if (map[i][j] == 1) {
				for (int size = 5; size >= 1; size--) {
					if (inRange(i, j, size)) {
						if (check_map(i, j, size) && cntPerSize[size] > 0) {
							cntPerSize[size]--;
							update_map(i, j, size, 0);							
							mincnt = min(solve(i, j, cnt + 1), mincnt);
							cntPerSize[size]++;
							update_map(i, j, size, 1);
						}
					}
				}
				return mincnt;
			}
		}
	}

	return mincnt;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

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

	int ans = solve(0,0,0);
	if (ans < 99999)
		cout << ans;
	else
		cout << -1;
}

개발 환경 : VS2017

질문, 지적 환영합니다!