[알고리즘 문제] 백준17136 - 색종이 붙이기

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

완전탐색(색종이를 하나씩 붙여보는 방식)으로 푸는 건 알고 있었는데 어떻게 코드로 옮겨야 할지 몰라 다른 분의 풀이를 참고하였습니다.

 

일단 재귀함수로 색종이를 계속 이어 붙이면서 기저조건은 다음과 같습니다.

1. x의 위치가 10인 경우 -> 다음 행으로 이동

2. y의 위치가 10인 경우 -> 사용한 색종이 개수 갱신(최소값으로)

3. arr[y][x]==0 인 경우 -> x+1로 이동

 

위의 조건을 모두 통과하면 이제 색종이를 붙일 건데 조건으로 색종이를 붙일 수 있고(해당 위치의 값이 0이 아니고), 붙였을 때 배열을 벗어나지 않아야 합니다. 

 

만약 위의 조건을 만족한다면, 재귀적으로 색종이를 붙여 나갑니다. 

 

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 10;

int ans = 987654321;
int cnt;
int arr[MAX][MAX] = {0};
int paper[6] = {0, 5, 5, 5, 5, 5};

void search(int y, int x)
{
    if (x == MAX) // 다음 줄 검사
    {
        search(y + 1, 0);
        return;
    }

    if (y == MAX) // 끝까지 다 검사했으면 사용한 개수와 ans중 최소값을 계산
    {
        ans = min(ans, cnt);
        return;
    }
    if (arr[y][x] == 0) // 0에는 색종이를 덮을 수 없기 때문에 다음 열로 이동
    {
        search(y, x + 1);
        return;
    }

    for (int len = 5; len >= 1; len--)
    { // 모든 가능한 경우의 색종이 수를 덮어본다

        if (paper[len] == 0 || y + len > MAX || x + len > MAX) // len크기의 색종이가 없거나 색종이를 덮었을 때 배열을 벗어나는 경우 예외처리
        {
            continue;
        }

        bool flag = true;
        for (int q = 0; q < len; q++) // 현재 시점에서 len 크기의 색종이로 덮을 수 있는지 검사
        {
            for (int w = 0; w < len; w++)
            {
                if (arr[y + q][x + w] == 0)
                {
                    flag = false;
                    break;
                }
            }
            if (!flag)
            {
                break;
            }
        }
        if (!flag) // 덮을 수 없다면 다음 크기의 색종이로 덮어봄
        {
            continue;
        }

        for (int q = 0; q < len; q++) // len 크기의 색종이로 덮음
        {
            for (int w = 0; w < len; w++)
            {
                arr[y + q][x + w] = 0;
            }
        }

        paper[len]--; // len 크기의 색종이를 사용
        cnt++;

        search(y, x + len);

        for (int q = 0; q < len; q++) // 다시 복원
        {
            for (int w = 0; w < len; w++)
            {
                arr[y + q][x + w] = 1;
            }
        }

        paper[len]++;
        cnt--;
    }
}

int main()
{
    for (int y = 0; y < 10; y++)
    {
        for (int x = 0; x < 10; x++)
        {
            cin >> arr[y][x];
        }
    }

    search(0, 0);
    if (ans == 987654321)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}