[백준] 17136 - 색종이 붙이기

전형적인 Brute Force 문제이다.

색종이를 큰사이즈부터 가능한 위치에 붙여넣고, 모두 붙였다면 최소값을 찾는 문제

원래 나는 stl을 안쓰고 문제를 푸는것을 선호하지만, 이 문제는 안쓰고는 시간초과가 날 것 같아서 vector를 사용했다

1. map을 순회하며 색종이를 붙일 수 있는 위치를 찾는다.

2. 큰사이즈(5x5) 부터 작은 사이즈(1x1)를 차례대로 붙이면서 다음으로 넘어간다.

3. 만약 더이상 붙일 자리가 없다면 최소값을 갱신

4. 붙이는 갯수가 답보다 커진다면 return

#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
 
int checkcnt[6];
int dab = INF;
 
void dfs(int d, int x_, int
 y_, int size, vector< vector<int> > map) {
    bool dabcheck = true;
    if (d > dab) return;
    for (int i = 0; i < 10; i++){
        for (int j = 0; j < 10; j++){
            if (map[i][j] == 1) { dabcheck = false; break;}
        }
        if(!dabcheck) break;
    }
    if (dabcheck) {
        dab = dab > d - 1 ? d - 1 : dab;
        if (dab == -1) dab = 0;
        return;
    }
    for (int i = y_; i < y_ + size; i++) {
        for (int j = x_; j < x_ + size; j++) {
            if (i >= 10 || j >= 10 || map[i][j] == 0) return;
            map[i][j] = 0;
        }
    }
    int x, y;
    bool flag = false;
    for (x = 0; x < 10; x++) {
        for (y = 0; y < 10; y++) {
            if (map[y][x] == 1) {
                flag = true;
                break;
            }
        }
        if (flag) break;
    }
    
    for (int i = 5; i >= 1; i--) {
        if (checkcnt[i] == 5) continue;
        checkcnt[i]++;
        dfs(d + 1, x, y, i, map);
        checkcnt[i]--;
    }
}
 
int main(void) {
    std::vector< std::vector<int> > map(10, vector<int>(10, 0));
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            cin >> map[i][j];
    dfs(0, 0, 0, 0, map);
    if (dab == INF) cout << -1 << endl;
    else cout << dab << endl;
    return 0;
}