[BOJ] 색종이 붙이기

[문제]

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

입력

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

출력

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

예제 입력 1 복사

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

예제 출력 1 복사

0

 

[풀이]

 

17136

맞았습니다!!

1988

32

C++14 / 수정

2634

1분 전

 

1) 그리디 + dfs 완탐

 

2) 1인 칸들은 fillSpace 벡터에 좌표를 넣어줬다. fillSpace를 기준으로 채워나간다. 

 

3) dfs 완탐을 사용할 때 파라미터로 [사용한 색종이의 수, 채운 칸의 수] 를 보냈다. 

채운 칸의 수가 10*10 에 있는 1의 수와 같을 때 최소값을 비교한다. 

 

4) fillSpace를 돌면서 1이 적힌 칸의 좌표를 가져오고 이미 색종이가 덮은 칸이면 다음 칸을 보러간다. 

색종이는 가장 큰 크기인 5*5 부터 차례대로 1*1 까지 붙여본다. 

 

색종이들은 최대 5개까지만 붙일 수 있으므로 pageCnt배열을 생성해서 현재까지 붙인 색종이의 수를 저장했다. 

만약, 지금 붙이려고 한 색종이가 이미 5번을 사용한 전적이 있다면 더 돌아볼 거 없다 다른 색종이를 선택한다. 

 

그렇지 않다면, 5*5를 예로 들어 설명한다면 

이렇게 상하좌우로 5칸씩 살펴보면 된다. 저 범위 안에 1이 아닌 칸이 있다면 바로 false를 리턴하고 다음 색종이로 넘어간다. 

모두 1이라면 저 범위의 모든 칸에 visited 표시를 하고 paperCnt를 1만큼 증가한다. 

-> dfs 재귀 호출 

채운 공간은 5*5 , 4*4, ...1*1 이기 때문에 현재까지 채운 칸에 j*j 만큼 더한 값을 보내준다. 

 

5) 백트래킹 

 

---

#include <iostream>
#include <vector>
#include <cmath>
 
#define N 11
#define INF 987654321
using namespace std;
 
int map[N][N], ans = INF;
bool visited[N][N];
 
int paperCnt[6];//각 색종이를 사용한 횟수를 저장 
 
typedef pair<int, int> pp;
vector<pp> fillSpace;
 
bool check(int x, int mx, int y, int my) {
    //mx, my는 max_x, max_y의 줄임으로 사용 
    if (mx > N-1 || my > N-1) return false;
 
    for (int i = x; i < mx; i++) {
        for (int j = y; j < my; j++) {
            if (visited[i][j]) return false;
            if (!map[i][j]) return false;
        }
    }
    return true;
}
void dfs(int cnt, int fill) {
    if (fill == fillSpace.size()) {
        ans = min(ans, cnt);
        return;
    }
    if (ans <= cnt) return; //이미 최대값을 넘어버림
 
    //5*5부터 차례대로 들어갈 수 잇는 곳을 채워간다.
    for (int i = 0; i < fillSpace.size(); i++) {
        int x = fillSpace[i].first;
        int y = fillSpace[i].second;
 
        if (visited[x][y]) continue; //이미 채워진 칸 
 
        for (int j = 5; j > 0; j--) {
            if (paperCnt[j] > 4) {
                //최대 5장까지만 사용 가능 
                continue; //다른 색종이 사용
            }
 
            int nx = x + j;
            int ny = y + j; //5*5 , 4*4 ... 이기 때문에 j만큼 늘려준다.
 
            if (check(x, nx, y, ny)) {
                //j종류의 색종이로 채워질 수 있는 공간이라면
                for (int k = x; k < nx; k++) {
                    for (int z = y; z < ny; z++) {
                        visited[k][z] = true; //방문 표시->채웠다는 의미
                    }
                }
                paperCnt[j]++; //색종이 하나 씀 
 
                dfs(cnt+1, fill + j*j); //j*j만큼 채웠음 
 
                ///////////백트래킹////////////////////
                for (int k = x; k < nx; k++) {
                    for (int z = y; z < ny; z++) {
                        visited[k][z] = false; //방문 표시->채웠다는 의미
                    }
                }
                paperCnt[j]--;
                ///////////백트래킹////////////////////
            }
        } 
        return;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    for (int i = 0; i < N-1; i++) {
        for (int j = 0; j < N-1; j++) {
            cin >> map[i][j];
            if (map[i][j]) fillSpace.push_back(pp(i, j)); 
        }
    }
    //input 
    dfs(0,0); //색종이를 사용한 횟수, 채운 칸의 수 
 
    if (ans == INF) ans = -1;
    cout << ans << '\n';
    return 0;
}