[Algorithm]Baekjoon 17136번 :: 색종이 붙이기

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
int arr[10][10] = { 0 };
 
bool CanPlacePaper(int y, int x, int size)
{
    int maxY = y + size - 1;
    int maxX = x + size - 1;
 
    if (maxY >= 10) return false;
    if (maxX >= 10) return false;
 
    for (int i = y; i <= maxY; ++i)
    {
        for (int j = x; j <= maxX; ++j)
        {
            if (arr[i][j] == 0) return false;
        }
    }
 
    return true;
}
 
void FillArrayRange(int y, int x, int size, int num)
{
    int maxY = y + size - 1;
    int maxX = x + size - 1;
 
    for (int i = y; i <= maxY; ++i)
    {
        for (int j = x; j <= maxX; ++j)
        {
            arr[i][j] = num;
        }
    }
}
 
int answer = 0x3f3f3f3f;
int placeCount = 0;
int oneCount = 0;
int paperCounts[6] = { 0,5,5,5,5,5 };
 
void DFS(int y, int x)
{
    if (oneCount == 0) // 다붙였으면
    {
        answer = min(answer, placeCount);
        return;
    }
 
    if (x == 10)
    {
        x = 0;
        ++y;
 
        if (y == 10) return;
    }
 
    if (placeCount >= answer) return;
 
    if (arr[y][x] == 1)
    {
        for (int i = 5; i >= 1; --i)
        {
            if (CanPlacePaper(y, x, i) && paperCounts[i] > 0) // 붙일수 있고, 해당크기 색종이도 아직 남아있으면
            {
                FillArrayRange(y, x, i, 0);
                ++placeCount;
                oneCount -= i * i;
                --paperCounts[i];
                
 
                DFS(y, x + 1);
 
                // 원상복구
                FillArrayRange(y, x, i, 1); 
                --placeCount;
                oneCount += i * i;
                ++paperCounts[i];
                
            }
        }
    }
    else
    {
        DFS(y, x + 1);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
 
    for (int i = 0; i < 10; ++i)
    {
        for (int j = 0; j < 10; ++j)
        {
            cin >> arr[i][j];
            
            if (arr[i][j] == 1) ++oneCount;
        }
    }
 
    DFS(0, 0);
 
    if (answer == 0x3f3f3f3f) cout << -1;
    else cout << answer;
}
 
 

 

연습으로 풀어볼만한 백트래킹 완전탐색문제이다.

 

색종이를 붙일 수 있는곳마다 각 사이즈의 색종이를 전부 붙이는 시도를한다. 

물론 해당사이즈의 색종이를 붙일 수 있는지 검사 후, 붙여야 한다.

붙이고 탐색을 진행하고, 해당 탐색이 끝난후엔 다시 값들을 복귀시켜야 한다는걸 잊지말자.

 

붙일 수 없으면 좌표이동만 시행한다.

 

골드2문제치고는 좀 쉬운문제라 생각된다.