17136번 색종이 붙이기

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

백트래킹 문제이다.

(0, 0)부터 시작하여 색종이(1 ~ 5)의 모든 경우를 따지면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
int Map[11][11], cp[6], Min = 2e9;
// cp[i] : i 크기의 색종이의 수
 
// 방문 처리라고 생각하면 된다.
void coloring(int y, int x, int c, int n)
{
    for (int i = y; i < y + c; i++) 
        for (int j = x; j < x + c; j++) 
            Map[i][j] = n;
}
 
// 붙일 수 있는지 검사
bool isStick(int y, int x, int c)
{
    for (int i = y; i < y + c; i++)
        for (int j = x; j < x + c; j++)
            if (!Map[i][j])
                return false;
    return true;
}
 
void backtracking(int total, int y, int x)
{
    // total이 이미 Min보다 클 경우 진행할 필요 없음.
    if (total > Min) return; 
 
    // x가 10 이상일 경우 다음 y(행)로 넘어간다.
    if (x >= 10) { x = 0; ++y; } 
 
    // y가 10 이상인 경우는 끝난 경우이므로, Min 갱신한다.
    if (y >= 10) { Min = min(Min, total); return; } 
 
    // 지금 순서가 0이라면, 다음 칸(열)으로 넘어간다.
    if (!Map[y][x]) { backtracking(total, y, x + 1); return; }
 
    // 좌표(y행, x열)에 대하여 색종이 1 ~ 5 모두 탐색
    for (int c = 1; c <= 5; c++)    
        if (isStick(y, x, c) && cp[c] < 5) 
        {
            // 색종이를 붙일 수 있고, 그 크기에 대한 수가 5가 아직 안 됐다면
            coloring(y, x, c, 0); ++cp[c];
            backtracking(total + 1, y, x + 1);
            coloring(y, x, c, 1); --cp[c];
        }
}
 
int main(void)
{
    for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) scanf("%d", &Map[i][j]);
    backtracking(0, 0, 0);
    printf("%d\n", Min == 2e9 ? -1 : Min);
 
    return 0;
}