백준 17136번: 색종이 붙이기
19643 단어 BacktrackingpscppBacktracking
색종이 붙이기
아이디어
색종이를 사이즈별로 붙이다가 더이상 붙일 수 없을 때 이전의 상태로 돌아가면 된다. 이 때 주의할 점이 몇가지 있다.
- 색종이를 붙였을 때 10x10 사이즈 종이 바깥으로 벗어나는지 확인.
- 같은 사이즈의 색종이는 5장까지 사용 가능하기 때문에 색종이가 남아있는지 확인.
- 색종이를 붙일 공간이 있는 지 확인.
코드
#include <bits/stdc++.h>
using namespace std;
bool arr[10][10];
int paper[5] = {5, 5, 5, 5, 5};
int space = 0;
int MIN = INT_MAX;
vector<pair<int, int>> v;
vector<pair<int,int>>::iterator iter;
bool check_safe(int y, int x) {
return y >= 0 && y < 10 && x >= 0 && x < 10;
}
void cover(int y, int x, int size, bool value) {
for (int i = y; i < y+size; i++) {
for (int j = x; j < x+size; j++) {
arr[i][j] = value;
}
}
if (value) { // uncover
space += (size*size);
paper[size-1] += 1;
}
else { // cover
space -= (size*size);
paper[size-1] -= 1;
}
}
bool check(int y, int x, int size) {
if (!check_safe(y+size-1, x+size-1)) return false;
if (paper[size-1] <= 0) return false;
for (int i = y; i < y+size; i++) {
for (int j = x; j < x+size; j++) {
if (arr[i][j] == 0) return false;
}
}
return true;
}
void solve(int cnt) {
if (space == 0) {
MIN = min(MIN, cnt);
return;
}
int y = (*iter).first;
int x = (*iter).second;
int idx = 0;
while (!arr[y][x]) {
iter++;
idx++;
y = (*iter).first;
x = (*iter).second;
}
for (int i = 1; i <= 5; i++) {
if (check(y, x, i)) {
cover(y, x, i, 0);
iter++;
solve(cnt+1);
cover(y, x, i, 1);
iter--;
}
}
iter -= idx;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cin >> arr[i][j];
if (arr[i][j] == true) {
space++;
v.push_back({i, j});
}
}
}
iter = v.begin();
solve(0);
if (MIN == INT_MAX) {
if (space) cout << -1;
else cout << 0;
}
else {
cout << MIN;
}
return 0;
}
여담
iterator에서 정수를 빼서 이전 상태로 돌아갈 수 있다는 사실!
Author And Source
이 문제에 관하여(백준 17136번: 색종이 붙이기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ks1ksi/백준-17136번-색종이-붙이기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)