[17136번] 색종이 붙이기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

2. BFS

완전 탐색을 통해 그냥 색종이를 계속 붙여가며 최소 몇개로 모두 0으로 만들 수 있는지 찾는 문제이다.

자세한 풀이 과정은 아래 주석을 통해 달아두었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
 
typedef pair<int, int> pii;
 
// 큐정보
// 맵, y,x,cnt, 색종이 남은 개수
struct INFO {
    int map[12][12];
    int y, x;
    int cnt;
    int colorPaper[6];
};
 
int arr[12][12];
pii point; // 첫좌표 받는 임시 변수
 
// 맵 복사 함수
void copyMap(int dest[][12], int src[][12]) {
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            dest[i][j] = src[i][j];
}
 
// 해당하는 시작 좌표에서 n크기의 사각형이 모두 1인지 확인
bool checkArea(int n, int y, int x, int map[][12]) {
    for (int i = y; i < y + n; i++)
        for (int j = x; j < x + n; j++)
            if (!(0 <= i && i < 10 && 0<= j && j < 10 && map[i][j]))
                return false;
    return true;
}
 
// 해당하는 시작 좌표에서 n크기의 사각형 지우기
void fillArea(int n, int y, int x, int map[][12]) {
    for (int i = y; i < y + n; i++)
        for (int j = x; j < x + n; j++)
            map[i][j] = 0;
}
 
// 모두 0으로 되어있는지 확인
bool isOnlyZero(int map[][12]) {
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            if (map[i][j])
                return false;
    return true;
}
int main() {
    point = { -1, -1 };
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++) {
            scanf("%d", &arr[i][j]);
            // 처음 1로 시작하는 좌표 받는다.
            if (arr[i][j] && point.first == -1)
                point = { i,j }; 
        }
 
    // 답이 없을때 -1이기에 ans = -1로 시작
    int ans = -1;
 
    INFO info;
    copyMap(info.map, arr);
    info.cnt = 0;
    info.y = point.first;
    info.x = point.second;
    // 색종이는 모두 5개있다.
    for (int i = 0; i < 6; i++)
        info.colorPaper[i] = 5;
 
    queue<INFO> q;
 
    q.push(info);
 
    while (!q.empty()) {
        INFO here = q.front();
        q.pop();
        int map[12][12];
        copyMap(map, here.map);
        int y = here.y;
        int x = here.x;
        int cnt = here.cnt;
        int colorPaper[6];
        for (int i = 0; i < 6; i++)
            colorPaper[i] = here.colorPaper[i];
        
        // ans가 갱신됐으며 cnt가 갱신된 ans보다 크면 볼필요 없다.
        if (ans != -1 && cnt > ans)
            continue;
 
        // 모두 다 지웠으면 ans 갱신
        if (isOnlyZero(map)) {
            if (ans == -1)
                ans = cnt;
            ans = min(ans, cnt);
        }
 
        // 크기 1~5짜리 색종이 하나씩 다 붙여보는 과정(완전탐색)
        for (int i = 1; i <= 5; i++) {
            // 색종이가 남아있고 해당 위치에 해당 크기 색종이 붙일 수 있으면
            if (colorPaper[i] - 1 >= 0 && checkArea(i, y, x, map)) {
                INFO tmp;
                copyMap(tmp.map, map);
                fillArea(i, y, x, tmp.map);
                tmp.cnt = cnt + 1;
                for (int j = 0; j < 6; j++)
                    tmp.colorPaper[j] = colorPaper[j];
                tmp.colorPaper[i] --;
 
                bool chk = false;
                for (int a = 0; a < 10; a++) {
                    for (int b = 0; b < 10; b++) {
                        // 처음 1로 시작하는 좌표 담아주고 break
                        if (tmp.map[a][b]) {
                            tmp.y = a;
                            tmp.x = b;
                            chk = true;
                            break;
                        }
                    }
                    if (chk)
                        break;
                }
 
                q.push(tmp);
            }
        }
    }
 
    printf("%d", ans);
    return 0;
}