백준 17136 : 색종이 붙이기 (c++)

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

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을 출력한다.

예제 입력 
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 1 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 0 1 1 1 1 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 1 1 1 1 1

예제 출력 
6

#include <iostream>
#include <algorithm>

using namespace std;

int map[10][10]; 
bool chk[10][10];
int color[6]={0,};
int res=30;

bool isOK(int y, int x, int size){

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

void dfs(int y, int x, int cnt){
    while(map[y][x]==0){
        if(++x>=10){
            if(++y>=10){
                res = min(res,cnt);
                return;
            }
            x=0;
        }
    }
    if(res<=cnt)    return;
    for(int s=5;s>0;s--){
        if(y+s>10||x+s>10||color[s]==5) continue;
        if(isOK(y,x,s)){
            update(y,x,s,0);
            color[s]++;
            dfs(y,x,cnt+1);
            update(y,x,s,1);
            color[s]--;
        }
    }
}

int main(){

    freopen("input.txt","r",stdin);

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

    dfs(0,0,0);
    if(res==30)  res=-1;
    cout<<res;
    return 0;
}