- 정확한 이유는 모르겠는데 처음에 맵을 탐색하다가 1을 발견하면 5가지의 색종이를 모두 붙이는 식으로
- 구현을 했었는데 계속 종료조건이 애매해서 어쩔 줄 몰라 하다가,,,, 탐색을 하는 부분이랑 색종이를 붙여보는
- 것을 나눠서 구현했더니 해결이 되었습니다.
- 자신감이 딱 붙어갈 타이밍에 좌절을 준 문제였습니다.....나중에 다시 풀어도 고생할 듯한....
- 전체적인 구조를 종료조건을 잘 생각해서 짜야할 것 같습니다.... 아이디어는 금방 떠올렸으나..참;;
- 개인적으로 힘든 문제였습니다..
2.주의사항
- 종료조건을 적절히 사용할 수 있게끔 전체적인 구조를 생각하고 짜자.....!
3.나의 코드
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int map[10][10];
int colorpaperset[6];
int minimumpapaer = 101;
void doattach(int, int, int);
void inputsetting() {
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++) {
cin >> map[i][j];
}
}
for (int i = 1; i < 6; i++) {
colorpaperset[i] = 5;
}
}
bool canattach(int x, int y, int r) {
if (x + r > 10 || y + r > 10) { return false; }
for (int i = x; i < x+r; i++) {
for (int j = y; j < y+r; j++) {
if (map[i][j] == 0) return false;
}
}
return true;
}
void setmap(int x, int y, int r) {
for (int i = x; i < x + r; i++) {
for (int j = y; j < y + r; j++) {
map[i][j] =0;
}
}
}
void unsetmap(int x, int y, int r) {
for (int i = x; i < x + r; i++) {
for (int j = y; j < y + r; j++) {
map[i][j] = 1;
}
}
}
void attach(int x, int y, int r) {
int tmpx, tmpy;
bool c = false;
for (int i = x; i < 10; i++) { //1인 부분을 탐색
for (int j = 0; j < 10; j++) {
if (map[i][j] == 0) {
if (i == 9 && j == 9) { minimumpapaer = min(minimumpapaer, r); return; }
// 재귀를 통해 여기까지 왔다는 것 자체가 이미 1을 다 0으로 바꾸고 도착했다는 것
continue;}
tmpx = i; tmpy = j; c = true; break;
}
if (c == true) break;
}
doattach(tmpx, tmpy, r);
}
void doattach(int x, int y, int r) {//붙이기를 시도한다.
for (int k = 5; k > 0; k--) {
if (canattach(x, y, k) == true && colorpaperset[k] > 0) {
setmap(x, y, k);
colorpaperset[k]--;
attach(x, y, r + 1); //재귀를 통해 다시 탐색을 수행
colorpaperset[k]++; //다른 종이에 대해서도 수행을 해봐야하므로
unsetmap(x, y, k); //원상 복구
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
inputsetting();
attach(0, 0, 0);
if (minimumpapaer == 101) { cout << -1; }
else { cout << minimumpapaer; }
return 0;
}
