[백준] 17136번. 색종이 붙이기

색종이를 붙이는 최소값을 찾는 문제다.

백트래킹과 DFS를 사용하면 생각보다 간단히 풀 수 있다.

가장 큰 색종이부터 작은 색종이를 찾으면서 푼다(5 4 3 2 1) 크기 5부터 시작해서 DFS로 들어가서 그 크기에 맞는지 확인을 하고 붙일 수 없다면 함수를 종료한다.

만약 색종이를 붙일 수 있다면 값을 0으로 바꾸고, 1인 위치를 찾는다. map에 1이 없다면 ans와 현재 붙인 색종이 개수를 비교해 작은 값을 ans에 저장한다.

 

 최소값을 저장 후 다음에 탐색할때, 최소값보다 붙인 색종이가 많아진다면 바로 함수를 종료한다.(백트래킹)

 

#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
vector<vector<bool>> visit;
int dxy[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int ans = 100000000;
int num[6] = { 0, };
 
void dfs(int a, int b, int dep, int size_, vector<vector<int>> map) {
    //백트래킹. 색종이를 사용하는 최소값을 구하는 것이기 때문에 ans보다 dep이 커지면 볼필요가 없다.
    if (ans < dep) return;
 
    //현재 크기에 맞는 색종이를 붙임. 0 -> 1
    for (int i = a; i < a + size_; i++) {
        for (int j = b; j < b + size_; j++) {
            if (i >= 10 || j >= 10 || map[i][j] == 0) return;
            map[i][j] = 0;
        }
    }
 
    //색종이를 다 붙였다면 최소값을 저장하고 return;
    bool end = false;
    int x, y;
    bool flag = false;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j] == 1) {
                end = true;
                x == i; y == j;
                break;
            }
        }
        if (end) break;
    }
    if (!end) {
        ans = ans < dep ? ans : dep;
        if (ans == -1) ans = 0;
        return;
    }
 
 
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j] == 1) {
                x = i; y = j;
                flag = true;
                break;
            }
        }
        if (flag) break;
    }
 
    //크기가 5인 색종이부터 시작해서 차례대로 작은 것을 검색
    for (int i = 5; i >= 1; i--) {
        if (num[i] == 5) continue;
        num[i]++;
        dfs(x, y, dep + 1, i, map);
        num[i]--;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<vector<int>> map;
    map.assign(10, vector<int>(10));
    visit.assign(10, vector<bool>(10, false));
    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 (ans == 100000000) {
        cout << "-1";
        return 0;
    }
    
    cout << ans;
    return 0;
}