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

 

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

 

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

17136번: 색종이 붙이기

---

 

해결전략

 

백트래킹 Backtracking

구현

---

 

처음 시도한 코드

 

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

int answer; // 색종이 최소 개수
vector<int> result(5, 0);

vector<vector<int>> v;
queue<pair<int, int>> Q;

bool isSquare(int y, int x, int ny, int nx)
{
	if (y < 0 || x < 0 || 10 <= ny || 10 <= nx) return false;

	for (int i = y; i <= ny; i++) {
		for (int j = x; j <= nx; j++) {
			if (v[i][j] == 0) return false;
		}
	}
	return true;
}

void Attach(int y, int x, int ny, int nx)
{
	for (int i = y; i <= ny; i++) {
		for (int j = x; j <= nx; j++) {
			v[i][j] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	v.resize(10, vector<int>(10));
	for (int y = 0; y < 10; y++) {
		for (int x = 0; x < 10; x++) {
			cin >> v[y][x];
			if (v[y][x] == 1) Q.push({ y, x });
		}
	}

	for (int i = 4; i >= 0; i--)
	{
		int size = Q.size();

		while (!Q.empty() && size--)
		{
			int y = Q.front().first;
			int x = Q.front().second;
			Q.pop();
					
			if (isSquare(y, x, y + i, x + i)) {
				if (i > 0 && result[i] >= 5) continue;
				else if (i == 0 && result[i] >= 5) {
					cout << "-1";
					return 0;
				}

				Attach(y, x, y + i, x + i);
				result[i]++;
			}
			else {
				Q.push({ y, x });
			}
		}
	}

	while (!Q.empty())
	{
		int y = Q.front().first;
		int x = Q.front().second;
		Q.pop();

		if (v[y][x] == 1) {
			cout << "-1";
			return 0;
		}
	}

	answer = result[0] + result[1] + result[2] + result[3] + result[4];
	cout << answer << "\n";

	return 0;
}

 

---

 

 

정답 코드

 

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

int answer = 1e9; // 색종이 최소 개수. 
vector<int> paper(5, 5); // 1x1부터 5x5까지 색종이 5장씩
vector<vector<int>> v(10, vector<int>(10)); // 10x10 종이

// 주어진 위치에서 특정 크기의 색종이를 붙일 수 있는지 확인
bool isSquare(int y, int x, int size) {
    if (y + size > 10 || x + size > 10) return false; 

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

void Attach(int y, int x, int size, int flip) {
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            v[i][j] = flip; // 영역을 flip 값으로 채움
        }
    }
}

// DFS를 사용하여 모든 가능한 색종이 붙이기 경우의 수를 탐색
void Cal(int y, int x, int cnt) 
{
    if (x >= 10) { // x가 10에 도달하면 다음 행으로 넘어갑
        Cal(y + 1, 0, cnt);
        return;
    }
    if (y >= 10) { // y가 10에 도달하면 모든 칸을 확인한 것이므로 최소값을 갱신
        answer = min(answer, cnt);
        return;
    }

    if (v[y][x] == 1) { // 현재 위치에 색종이를 붙일 수 있다면 모든 가능한 크기의 색종이를 시도
        for (int k = 0; k < 5; k++) {
            if (paper[k] > 0 && isSquare(y, x, k + 1)) // 색종이 크기 k+1로 수정
            { 
                Attach(y, x, k + 1, 0); // k+1 크기로 색종이 붙임
                paper[k]--;

                Cal(y, x + 1, cnt + 1); // 다음 칸으로 넘어감

                Attach(y, x, k + 1, 1); // 붙였던 색종이를 제거
                paper[k]++;
            }
        }
    }
    else {  // 현재 위치에 색종이를 붙일 필요가 없다면 다음 칸으로 넘어감
        Cal(y, x + 1, cnt);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    for (int y = 0; y < 10; y++) {
        for (int x = 0; x < 10; x++) {
            cin >> v[y][x];
        }
    }

    Cal(0, 0, 0);

    if (answer == 1e9) cout << "-1";
    else cout << answer;

    return 0;
}

 

---