백준 17136번 [색종이 붙이기](C++) -yes6686- 티스토리

백준 문제 풀이: 17136 [색종이 붙이기]

---

문제 링크: https://www.acmicpc.net/problem/17136

문제 설명:

10×10 크기의 보드에서 각 칸은 1(붙여야 하는 칸) 또는 0(비어 있는 칸)으로 이루어져 있습니다. 1로 표시된 모든 칸을 최소 개수의 색종이를 이용해 덮어야 합니다. 색종이는 크기별로 1×1, 2×2, 3×3, 4×4, 5×5가 있으며 각 크기의 색종이는 최대 5장씩 사용할 수 있습니다.

모든 칸을 덮을 수 없으면 -1을 출력하고, 덮을 수 있으면 사용된 색종이의 최소 개수를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[10][10];

/* 다섯 종류의 색종이 갯수 초기화*/
int leftSquare1x1Cnt = 5;
int leftSquare2x2Cnt = 5;
int leftSquare3x3Cnt = 5;
int leftSquare4x4Cnt = 5;
int leftSquare5x5Cnt = 5;

int ans = 26;

int isSquareNxN(int a, int b, int N) { // N*N의 칸에 모두 1이 들어있는지 확인
    int cnt = 0;
    if (a + N > 10 || b + N > 10) return 0; // 종이의 경계 밖으로 나가는 경우
    for (int i = a; i < a + N; i++) {
        for (int j = b; j < b + N; j++) {
            if (arr[i][j] == 1) cnt++;
        }
    }
    return cnt == N * N ? 1 : 0;
}

void SquareNxNChangeToZero(int a, int b, int N) { // N*N칸의 원소를 0으로 초기화
    for (int i = a; i < a + N; i++) {
        for (int j = b; j < b + N; j++) {
            arr[i][j] = 0;
        }
    }
}

void SquareNxNChangeToOne(int a, int b, int N) { // N*N칸의 원소를 1으로 초기화
    for (int i = a; i < a + N; i++) {
        for (int j = b; j < b + N; j++) {
            arr[i][j] = 1;
        }
    }
}

void solve(int a, int b, int u) {
    if (ans < u) return;
    if (a == 10) {
        int isAllZero = 1;
        for (int i = 0; i < 10; i++) { // 모든 원소가 0인지 확인
            for (int j = 0; j < 10; j++) {
                if (arr[i][j] != 0) {
                    isAllZero = 0;
                    break;
                }
            }
            if (isAllZero == 0) break;
        }
        if (isAllZero == 1) { // 모든 원소가 0인 경우
            if (ans > u) { // 필요한 색종이의 최소 개수 구하기
                ans = u;
            }
        }
        return;
    }
    if (arr[a][b] == 1) {
        for (int N = 5; N >= 1; N--) {
            if (isSquareNxN(a, b, N) == 1) { 
                if (N == 1 && leftSquare1x1Cnt > 0) {
                    leftSquare1x1Cnt--;
                    SquareNxNChangeToZero(a, b, N);
                    solve(b == 9 ? a + 1 : a, b == 9 ? 0 : b + 1, u + 1);
                    SquareNxNChangeToOne(a, b, N);
                    leftSquare1x1Cnt++;
                } else if (N == 2 && leftSquare2x2Cnt > 0) {
                    leftSquare2x2Cnt--;
                    SquareNxNChangeToZero(a, b, N);
                    solve(b == 9 ? a + 1 : a, b == 9 ? 0 : b + 1, u + 1);
                    SquareNxNChangeToOne(a, b, N);
                    leftSquare2x2Cnt++;
                } else if (N == 3 && leftSquare3x3Cnt > 0) {
                    leftSquare3x3Cnt--;
                    SquareNxNChangeToZero(a, b, N);
                    solve(b == 9 ? a + 1 : a, b == 9 ? 0 : b + 1, u + 1);
                    SquareNxNChangeToOne(a, b, N);
                    leftSquare3x3Cnt++;
                } else if (N == 4 && leftSquare4x4Cnt > 0) {
                    leftSquare4x4Cnt--;
                    SquareNxNChangeToZero(a, b, N);
                    solve(b == 9 ? a + 1 : a, b == 9 ? 0 : b + 1, u + 1);
                    SquareNxNChangeToOne(a, b, N);
                    leftSquare4x4Cnt++;
                } else if (N == 5 && leftSquare5x5Cnt > 0) {
                    leftSquare5x5Cnt--;
                    SquareNxNChangeToZero(a, b, N);
                    solve(b == 9 ? a + 1 : a, b == 9 ? 0 : b + 1, u + 1);
                    SquareNxNChangeToOne(a, b, N);
                    leftSquare5x5Cnt++;
                }
            }
        }
    } else {
        solve(b == 9 ? a + 1 : a, b == 9 ? 0 : b + 1, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> arr[i][j];
        }
    }
    solve(0, 0, 0);
    cout << (ans == 26 ? -1 : ans);
}

---

코드 설명

• 핵심 알고리즘: 백트래킹을 사용해 색종이를 붙일 수 있는 모든 경우를 탐색하며 최소 개수를 구합니다.
• 구현 세부사항:
  • 각 크기(1x1 ~ 5x5)의 색종이를 순차적으로 붙이며 재귀적으로 탐색
  • 모든 칸이 0이 되면 최적 해를 갱신
• 시간 복잡도 분석: O(5ⁿ) (최악의 경우 모든 색종이를 탐색)

---

결과

10×10 보드에서 모든 1을 최소 개수의 색종이로 덮는 방법을 계산합니다. 불가능한 경우 -1을 출력합니다. 백트래킹과 재귀를 활용하여 효율적으로 풀이했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!