[백준][BOJ][C++][17136번] 색종이 붙이기

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

17136번: 색종이 붙이기

dfs를 이용하여 풀었습니다.

dfs를 사용할때 가지치기를 똑바로 하지 않으면 시간초과가 발생하여 아래 코드에서 if (out == true) break; 이부분이 중요하였습니다.

#include<iostream>
#include<algorithm>
using namespace std;
 
int ans, cnt;
int paper[11][11];
int paper_cnt[6];
 
bool pa_ch(int x, int y, int sizee) {
    for (int Y = y; Y < y + sizee; Y++) {
        for (int X = x; X <x + sizee; X++) {
            if (paper[Y][X] == 0)
                return false;
        }
    }
    return true;
}
 
void dfs(int ans_temp, int x, int y, int cnt_temp) {
    if (ans_temp > ans) return;
    if (cnt_temp == cnt) {
        ans = ans_temp;
        return;
    }
    if (ans_temp == 25) return;
    bool out = false;
    for (int Y = y; Y < 10; Y++) {
        for (int X = x; X < 10; X++) {
            if (paper[Y][X] == 1) {
                out = true;
                for (int i = 5; i >= 1; i--) { //1x1부터 5x5까지 탐색
                    if (paper_cnt[i] == 0) continue;
                    if (paper_cnt[i] == 0 && i == 1) return;
                    if (!pa_ch(X, Y, i)) continue;
 
                    paper_cnt[i]--;
                    int gob = i*i;
                    for (int YY = Y; YY < Y + i; YY++) {
                        for (int XX = X; XX < X + i; XX++) {
                            paper[YY][XX] = 0;
                        } //for XX
                    } // for YY
 
                    dfs(ans_temp + 1, X, Y, cnt_temp + gob);
 
                    paper_cnt[i]++;
                    for (int YY = Y; YY < Y + i; YY++) {
                        for (int XX = X; XX <X + i; XX++) {
                            paper[YY][XX] = 1;
                        }//for XX
                    }//for YY
 
                }  //for i
            } //if paper
            if (out == true) break;
        } //for X
        if (out == true) break;
        x = 0;
    } //for Y
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cnt = 0;
    for (int i = 1; i < 6; i++) paper_cnt[i] = 5; //색종이 갯수 넣기
 
    for (int Y = 0; Y < 10; Y++) {
        for (int X = 0; X < 10; X++) {
            scanf("%d", &paper[Y][X]);
            //cin >> paper[Y][X];
            if (paper[Y][X] == 1) cnt++;
        }
    }
    ans = 40;
    dfs(0, 0, 0, 0);
    if (ans == 40)
        printf("-1");
        //cout << "-1";
    else
        printf("%d",ans);
        //cout << ans;
}