색종이 붙이기

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 0713 ~ 0917
int ans=1e9;
int board[12][12];
int paper[6] = {0, 5,5,5,5,5};
bool checkEnd()
{
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            if(board[i][j] == 1) return false;
    return true;
}
bool checkSize(int r, int c, int size)
{
    for(int i=r;i<r+size;i++)
    {
        for(int j=c;j<c+size;j++)
        {
            if(i<0 or j<0 or i>=10 or j>=10) return false;
            if(board[i][j] == 0) return false;
        }
    }
    return true;
}
void putPaper(int r, int c, int size)
{
    for(int i=r;i<r+size;i++)
        for(int j=c;j<c+size;j++)
            board[i][j] = 0;
}
void getPaper(int r, int c, int size)
{
    for(int i=r;i<r+size;i++)
        for(int j=c;j<c+size;j++)
            board[i][j] = 1;
}
void DFS(int r, int count)
{
    if(checkEnd()){
        ans = min(ans, count);
        return;
    }
    for(int i=r;i<10;i++)
    {
        for(int j=0;j<10;j++)
        {
            if(board[i][j] == 0) continue;
            for(int size=5;size>=1;size--)
            {
                if(paper[size] > 0 and checkSize(i,j,size)){
                    paper[size]--;
                    putPaper(i, j, size);
                    DFS(i, count + 1);
                    getPaper(i, j, size);
                    paper[size]++;
                }
            }
            /* 무조건 하나의 1에 대해서만 실행하기 때문에 종료 */
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++)
            cin >> board[i][j];
    DFS(0, 0);
    if(ans == 1e9) ans = -1;
    cout << ans;
    return 0;
}

• 핵심
  : 모든 1에 대해서 모든 종류의 색종이 크기에 대해 가능하다면 백트래킹을 수행해서 최소값을 찾는다

• 느낀 점
  : 하나의 DFS는 하나의 1에 대해서만 수행하고 종료되어야 한다
  (그렇지 않으면 색종이를 덮지 않은채로 다음이 진행될 수 있음 + 시간복잡도 상승)