색종이 붙이기

일단 너무 어렵다 강의들어도 잘 이해가 안감.

내일 다시 복습하고 분석해야할듯

백트래킹

완탐 + 가지치기

인간미가 들어간 완전탐색이다.

이문제는 "최소"를 구하는 문제이다.

최소를 구할 때는 "최대" -> "최소"

최대를 구할 때는 "최소" -> "최대"

문제 조건에 따라

int일 경우 : const int INF = 987654321;
long long일 경우 : const int INF = 1e18

현재 DFS를

이런식으로 돌릴것이다.

CPP코드

#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define endl "\n"

const int INF = 987654321;
int a[104][104], ret = INF, n = 10;
map<int, int> mp;

bool Check(int y, int x, int cnt)
{
    if (y + cnt > n || x + cnt > n) return false;
    for (int i = y; i < y + cnt; ++i)
    {
        for (int j = x; j < x + cnt; ++j)
        {
            if (a[i][j] == 0) return false;
        }
    }
    return true;
}

void Draw(int y, int x, int cnt, int value)
{
    for (int i = y; i < y + cnt; ++i)
    {
        for (int j = x; j < x + cnt; ++j)
        {
            a[i][j] = value;
        }
    }
}

void DFS(int y, int x, int cnt)
{
    if (cnt >= ret) return;
    if (x == n) 
    {
        DFS(y + 1, 0, cnt);
        return;
    }
    if (y == n)
    {
        ret = min(cnt, ret);
        return;
    }
    if (a[y][x] == 0)
    {
        DFS(y, x + 1, cnt); return;
    }
    for (int _size = 5; _size >= 1; _size--)
    {
        if (mp[_size] == 5) continue;
        if (Check(y, x, _size))
        {
            ++mp[_size];
            Draw(y, x, _size, 0);
            DFS(y, x + _size, cnt + 1);
            Draw(y, x, _size, 1);
            --mp[_size];
        }
    }
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int y = 0; y < 10; ++y)
        for (int x = 0; x < 10; ++x)
            cin >> a[y][x];
    
    DFS(0, 0, 0);
    cout << (ret == INF ? -1 : ret) << endl;
    

    return 0;
}