백준 17136 색종이 붙이기 (C++)

17136번: 색종이 붙이기

백트래킹을 이용한 문제이다. 먼저 전체 맵을 5의 크기를 가지는 색종이부터 붙이고 다음 4,3,2,1 순으로 붙여준다. 그리고 백트래킹을 이용해 최솟값을 찾아주어 출력해주었다. 각각의 색종이의 개수가 5개라는 점을 조건으로 넣어주어야만 한다. 매번 dfs마다 1의 위치를 찾아주어 조건에 만족할 경우 색종이를 붙여주고 0으로 바꿔준다. 만약 1을 찾지 못한다면 최솟값을 구해 종료해준다.
생각보다 오래 걸린 문제였다. 완전 탐색을 한다는 점은 생각을 햇었는데 이를 구현하는 데에서 오래 걸렸고 자잘한 오타도 한 몫 했었다... 생각한 아이디어를 구현하는 데 있어서 차근차근 접근해야한다는 점을 인지하자.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int A[10][10], result = 1e9;
int paper[6];

bool checkSquare(int y, int x, int size) {
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            if (!A[i][j]) return false;
        }
    }
    return true;
}

void changeMap(int y, int x, int size, int tf) {
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            A[i][j] = tf;
        }
    }
}

void dfs(int y, int x, int count) {
    while (!A[y][x]) {
        x++;
        if (x >= 10) {
            y++;
            if (y >= 10) {
                result = min(result, count);
                return;
            }
            x = 0;
        }
    }

    if (result <= count) return;

    for (int i = 5; i >= 1; i--) {
        if (y + i > 10 || x + i > 10) continue;
        if (paper[i] == 5) continue;
        if (!checkSquare(y, x, i)) continue;

        paper[i]++;
        changeMap(y, x, i, 0);
        dfs(y, x, count + 1);
        paper[i]--;
        changeMap(y, x, i, 1);
    }
}

void solution() {
    dfs(0, 0, 0);

    if (result == 1e9) result = -1;
    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> A[i][j];
        }
    }

    solution();

    return 0;
}