[BOJ] - 17136. 색종이 붙이기

[URL]

https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

[문제 풀이]

 

* 재귀 DFS

 

1. map[][] == 1인부분 vector v에 info형태(x, y)로 저장

2. v의 갯수만큼 완전 탐색 검사 실시

3.  check[cx][cy] 현재 위치 이미 업데이트 된 곳인가?

4. isPossible() n==5부터 현 위치와 n사이즈를 가능 여부 체크

5. checkUp(cx, cy, n, 1) 현재 위치 부터 nxn만큼 1로 업데이트

 

 

[소스 코드]

 

#include <stdio.h>
#include <vector>
 
using namespace std;
 
// type
struct info {
    int x;
    int y;
};
 
// variable
vector <info> v;
int paper[5] = { 5, 5, 5, 5, 5 };
int map[10][10];
bool check[10][10] = { 0, };
int cand[987654];
int candCnt = 0;
 
// func
void init();
bool isPossible(int x, int y, int nSize);
void checkUp(int x, int y, int nSize, int value);
void go(int pos);
 
int main()
{
    init();
 
    go(0);
 
    if (candCnt != 0)
    {
        int Min = 987654;
        for (int i = 0; i < candCnt; i++)
        {
            if (cand[i] <= Min)
            {
                Min = cand[i];
            }
        }
        printf("%d\n", Min);
    }
    else
        printf("-1\n");
 
    return 0;
}
 
void init()
{
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            scanf("%d", &map[i][j]);
 
            if (map[i][j] == 1)
            {
                info temp;
                temp.x = i;
                temp.y = j;
 
                v.push_back(temp);
            }
        }
    }
}
 
bool isPossible(int x, int y, int nSize)
{
    if (paper[nSize - 1] < 1)
        return false;
 
    for (int i = x; i < x + nSize; i++)
    {
        for (int j = y; j < y + nSize; j++)
        {
            if (i < 0 || j < 0 || i >= 10 || j >= 10)
                return false;
 
            if (map[i][j] != 1)
                return false;
 
            if (check[i][j])
                return false;
        }
    }
 
    return true;
}
 
void checkUp(int x, int y, int nSize, int value)
{
    for (int i = x; i < x + nSize; i++)
    {
        for (int j = y; j < y + nSize; j++)
        {
            check[i][j] = value;
        }
    }
}
 
void go(int pos)        // map[][] == 1인 곳 완전탐색
{
    if (pos == v.size())
    {
        int sum = 0;
        for (int i = 0; i < 5; i++)
        {
            sum += paper[i];
        }
        cand[candCnt++] = 25 - sum;
 
        return;
    }
 
    int cx = v[pos].x;
    int cy = v[pos].y;
 
    if (check[cx][cy])        // 현 위치가 이미 업데이트 된 곳인가?
        go(pos + 1);
 
    for (int n = 5; n > 0; n--)
    {
        if (isPossible(cx, cy, n))        // 현 위치와 n사이즈 검사
        {
            paper[n - 1]--;        // n사이즈 색종이 갯수 -1
            checkUp(cx, cy, n, 1);        // 현 위치 업데이트
 
            go(pos + 1);
 
            checkUp(cx, cy, n, 0);        // 현 위치 업데이트 취소
            paper[n - 1]++;        // n사이즈 색종이 갯수 +1
        }
    }
}