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

백준의 색종이 붙이기(17136) 문제이다. (수정완료)

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 주어진 맵을 1x1 ~ 5x5 각 5장의 색종이들로 채울 수 있는지 구하는 문제이다.

    본인은 재귀를 이용한 백트래킹 방식으로 구현해 보았다.

    재귀의 매개변수로는 어떤 변수들이 사용됬는지, 재귀를 호출하면서 더 해줘야 할 과정이 무엇이 있는지 알아보자.

   

2) 먼저, 모든 칸은 1x1로 채울 수 있다. 또한, NxN(N = 1 ~ 5)짜리 색종이로 붙일 수 있다면, 1x1 ~ N-1xN-1 짜리

    색종이로도 그 칸을 채울 수 있다. 

     위의 그림과 같이 빨강칸이 현재 점이고, 저 칸을 통해서 알아낸 결과 3x3짜리 색종이 까지 붙일 수 있다는

     결론이 나온다면, 저 현재점으로부터 1x1, 2x2칸 짜리 색종이 또한 붙일 수 있다는 의미이다.

    

     본인은 재귀 함수(본문함수명 : DFS)에는 총 7개의 매개변수를 호출해주었다.

     각 매개변수는 (현재 Idx, 사용한 1x1짜리 색종이갯수, 2x2, 3x3, 4x4, 5x5짜리 갯수, 현재까지 채운 갯수)

     이렇게 7개를 호출해 주었다.

     1x1 ~ 5x5짜리 사용한 갯수는 말 그대로이고, 현재 Idx와 현재까지 채운 갯수를 알아보자.

     본인은 맵에서 주어지는 채워야 하는 부분(맵에서 '1'의 값을 갖는 부분)의 좌표들을 Vector에 입력과 동시에

     저장해 주었다. 즉, Vector의 0번 Index부터 마지막 Index까지 1에 대한 좌표들이 저장되어 있다는 것이다.

     가장 첫 호출은, (0, 0, 0, 0, 0, 0, 0)이다. 0번 Idx부터 시작한다는 것이다.

     이 후, DFS함수 안에서는 "현재 점에서부터 채울 수 있는 색종이의 최대 크기" 를 구해온다.

     즉, 그 최대크기가 3이라면, 3x3짜리 색종이를 넣을 수 있다는 의미이다. 하지만, 위에서도 말했듯이

     3x3짜리 색종이를 넣을 수 있다고해서 그 부분에 무조건 3x3짜리 색종이가 들어간다 ! 라고 못박아 버리면

     안된다. 그 자리에는 1x1짜리도, 2x2짜리 색종이도 들어갈 수 있다는 것에 명심하자.

     최대크기를 받아온 후에는, 다시 재귀를 호출하는데 재귀를 여러번 호출해준다.

     1 ~ 최대크기 까지에 대한 호출을 해준다는 것이다.

    

     또 한가지 중요한 것이 이미 칠한 칸은 중복해서 칠하면 안된다는 것이다. 이 부분을 위해서 본인은

     Visit[][] 배열로 중복 처리를 해 주었다. 그렇다면, 이제 칠하려는 부분을 Visit배열로 어떻게 표현해줄까?

     이게 1x1이라면, 현재 좌표만 Visit[][] = true로 표시해주면 그만인데, 예를 들어서 4x4짜리 색종이를

     붙이려면 어떻게 어떻게 Visit[][] 배열에 표시를 해줘야할까??

     현재 좌표로부터 총 16칸(4x4)을 모두 true로 표시를 해줘야 한다.

     따라서 본인은 이 부분을 Make_Visit() 라는 함수를 만들어서 Visit배열을 체크해주고 해제해주도록 하였다.

    

     매개변수의 가운데에 있는 1x1 ~ 5x5 짜리 색종이를 사용한 갯수는, 내가 사용하려는 색종이를 사용할 때마다

     +1 씩 해줘서 재귀를 호출하면 된다. 그렇다면, 마지막 매개변수인 현재까지 채운 갯수는 어떻게 해줘야 할까?

     1x1 색종이를 붙일때에는 +1, 2x2 색종이를 붙일 때에는 +4, 3x3짜리 색종이를 붙일때에는 +9, ... +16 ... +25

     이런식으로 호출해주면 된다.

     그렇게되면 반드시 이런 문제가 발생할 것이다. 내가 이전에 어떤 좌표에서 특정 크기의 색종이를 붙이면서

     이미 칠해진 좌표에 DFS가 호출되는 경우가 발생할 것이다.

     예를 들어서 (0, 0)에서 2x2짜리 색종이를 붙여서 (0, 0), (0, 1), (1, 0), (1, 1) 이렇게 4좌표가 이미 칠해졌다고

     표시되어 있을 때, (0, 1)이 호출되면 어떻게 될까 ????

     이미 칠해져 있으므로 그냥 넘어가줘야 한다. 즉, 이 경우에는 DFS(Idx + 1, 그대로 ~~ ) 를 호출하게 해 주었다.

    

     재귀의 종료조건은 크게 2가지이다.

     1. 현재 사용한 색종이의 갯수가 기존의 정답 갯수보다 많아지는 경우

     -> 더 진행해봤자, 어차피 색종이만 더 나올 뿐 절대 최소값이 될 수 없는 경우이기 때문이다.

     2. 모든 칸을 다 칠한 경우

     -> 함수의 마지막 매개변수를 이용한 종료조건이다. 모든 칸을 다 칠했다면 기존의 값과 비교하여 최소값을

         갱신시켜주고 탐색을 종료하면 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
 
#define endl "\n"
#define MAX 10
using namespace std;
 
int Answer = 987654321, Total_Cnt;
int MAP[MAX][MAX];
bool Visit[MAX][MAX];
bool Already_Answer = true;
vector<pair<int, int>> V;
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> MAP[i][j];
            if (MAP[i][j] == 1)
            {
                V.push_back(make_pair(i, j));
                Total_Cnt++;
                Already_Answer = false;
            }
        }
    }
}
 
bool Can_Fill(int x, int y, int r)
{
    int Cnt = 0;
    for (int i = x; i < x + r; i++)
    {
        if (i >= MAX) break;
        for (int j = y; j < y + r; j++)
        {
            if (j >= MAX) break;
            if (MAP[i][j] == 1 && Visit[i][j] == false)
            {
                Cnt++;
            }
        }
    }
 
    if (Cnt == r * r) return true;
    else return false;
}
 
int Find_Range(int x, int y)
{
    if (Can_Fill(x, y, 2) == true)
    {
        if (Can_Fill(x, y, 3) == true)
        {
            if (Can_Fill(x, y, 4) == true)
            {
                if (Can_Fill(x, y, 5) == true)
                {
                    return 5;
                }
                return 4;
            }
            return 3;
        }
        return 2;
    }
    return 1;
}
 
void Make_Visit(int x, int y, int r, bool t)
{
    for (int i = x; i < x + r; i++)
    {
        for (int j = y; j < y + r; j++)
        {
            Visit[i][j] = t;
        }
    }
}
 
void DFS(int Idx, int One, int Two, int Three, int Four, int Five, int Total)
{
    int Use = One + Two + Three + Four + Five;
 
    if (Answer < Use) return;
    if (Total == Total_Cnt)
    {
        Answer = Min(Answer, Use);
        return;
    }
    if (Visit[V[Idx].first][V[Idx].second] == true)
    {
        DFS(Idx + 1, One, Two, Three, Four, Five, Total);
        return;
    }
 
    int Can_Fill = Find_Range(V[Idx].first, V[Idx].second);
    if (Can_Fill == 1)
    {
        if (One + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 1, true);
            DFS(Idx + 1, One + 1, Two, Three, Four, Five, Total + 1);
            Make_Visit(V[Idx].first, V[Idx].second, 1, false);
        }
    }
    else if (Can_Fill == 2)
    {
        if (Two + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 2, true);
            DFS(Idx + 1, One, Two + 1, Three, Four, Five, Total + 4);
            Make_Visit(V[Idx].first, V[Idx].second, 2, false);
        }
 
        if (One + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 1, true);
            DFS(Idx + 1, One + 1, Two, Three, Four, Five, Total + 1);
            Make_Visit(V[Idx].first, V[Idx].second, 1, false);
        }
    }
    else if (Can_Fill == 3)
    {
        if (Three + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 3, true);
            DFS(Idx + 1, One, Two, Three + 1, Four, Five, Total + 9);
            Make_Visit(V[Idx].first, V[Idx].second, 3, false);
        }
 
        if (Two + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 2, true);
            DFS(Idx + 1, One, Two + 1, Three, Four, Five, Total + 4);
            Make_Visit(V[Idx].first, V[Idx].second, 2, false);
        }
 
        if (One + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 1, true);
            DFS(Idx + 1, One + 1, Two, Three, Four, Five, Total + 1);
            Make_Visit(V[Idx].first, V[Idx].second, 1, false);
        }    
    }
    else if (Can_Fill == 4)
    {
        if (Four + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 4, true);
            DFS(Idx + 1, One, Two, Three, Four + 1, Five, Total + 16);
            Make_Visit(V[Idx].first, V[Idx].second, 4, false);
        }
 
        if (Three + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 3, true);
            DFS(Idx + 1, One, Two, Three + 1, Four, Five, Total + 9);
            Make_Visit(V[Idx].first, V[Idx].second, 3, false);
        }
 
        if (Two + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 2, true);
            DFS(Idx + 1, One, Two + 1, Three, Four, Five, Total + 4);
            Make_Visit(V[Idx].first, V[Idx].second, 2, false);
        }
 
        if (One + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 1, true);
            DFS(Idx + 1, One + 1, Two, Three, Four, Five, Total + 1);
            Make_Visit(V[Idx].first, V[Idx].second, 1, false);
        }
    }
    else if (Can_Fill == 5)
    {
        if (Five + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 5, true);
            DFS(Idx + 1, One, Two, Three, Four, Five + 1, Total + 25);
            Make_Visit(V[Idx].first, V[Idx].second, 5, false);
        }
 
        if (Four + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 4, true);
            DFS(Idx + 1, One, Two, Three, Four + 1, Five, Total + 16);
            Make_Visit(V[Idx].first, V[Idx].second, 4, false);
        }
 
        if (Three + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 3, true);
            DFS(Idx + 1, One, Two, Three + 1, Four, Five, Total + 9);
            Make_Visit(V[Idx].first, V[Idx].second, 3, false);
        }
 
        if (Two + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 2, true);
            DFS(Idx + 1, One, Two + 1, Three, Four, Five, Total + 4);
            Make_Visit(V[Idx].first, V[Idx].second, 2, false);
        }
 
        if (One + 1 <= 5)
        {
            Make_Visit(V[Idx].first, V[Idx].second, 1, true);
            DFS(Idx + 1, One + 1, Two, Three, Four, Five, Total + 1);
            Make_Visit(V[Idx].first, V[Idx].second, 1, false);
        }        
    }
}
 
void Solution()
{
    if (Already_Answer == true)
    {
        cout << 0 << endl;
        return;
    }
    
    DFS(0, 0, 0, 0, 0, 0, 0);
    if (Answer == 987654321) Answer = -1;
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}