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

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

17136번: 색종이 붙이기

<풀이>

1. 종이 상태를 입력받는다.

2. 종이의 모든 1을 덮는데 필요한 색종이의 최소 갯수를 출력한다.

 

<해법>

1. 알고리즘 선택하기

=> 큰 색종이부터 먼저 붙이는 그리디한 방식으로 불가능합니다. 왜냐하면, 6x6을 최소로 덮는 방법은 5x5를 사용하는 것이 아닌, 3x3을 사용하는 것이기 때문입니다. 그러므로, 색종이를 붙여야하는 곳에 5가지 색종이를 모두 붙여보아야 합니다. 따라서, 저는 브루트포스를 선택했습니다.

 

2. 구현 방법 떠올리기

=> 아래는 구현 전에 저가 미리 생각한 것입니다.

(1) 브루트포스 중 DFS를 선택하고, 재귀함수로 구현한다.

(2) 종이의 좌표를 순차적으로 탐색하면서, 1인 부분에 5가지 색종이를 모두 덮어본다.

(3) 종이를 모두 탐색하면 함수는 종료된다.

자세한 구현은 아래 코드를 참조해주세요.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int N;
int map[10][10];
bool covered[10][10];
int cnt[6];
int answer;
 
bool canCover(int x, int y, int length) {
    //종이를 다 쓴 경우
    if (cnt[length] == 5) return false;
    //범위 벗어난 경우
    if (x + length > N || y + length > N) return false;
    //0을 덮거나, 이미 덮여져 있는 경우
    for (int i = x; i < x + length; i++) {
        for (int j = y; j < y + length; j++) {
            if (map[i][j] == 0 || covered[i][j]) return false;
        }
    }
    return true;
}
 
void cover(int x, int y, int length, bool type) {
    for (int i = x; i < x + length; i++) {
        for (int j = y; j < y + length; j++) {
            covered[i][j] = type;
        }
    }
}
 
void getNxt(int& x, int& y) {
    if (y == 9) x++, y = 0;
    else y++;
}
 
int coverPaper(int x, int y, int sum) {
 
    if (x == N) return sum;
 
    int ret = INF;
    //색종이를 붙여야 하는 경우
    if (map[x][y] == 1 && !covered[x][y]) {
        for (int i = 1; i <= 5; i++) {
            if (canCover(x, y, i)) {
                cover(x, y, i, true);
                cnt[i]++;
                int nx = x, ny = y;
                getNxt(nx, ny);
                ret = min(ret, coverPaper(nx, ny, sum + 1));
                cover(x, y, i, false);
                cnt[i]--;
            }
        }
    }
    else {
        int nx = x, ny = y;
        getNxt(nx, ny);
        ret = coverPaper(nx, ny, sum);
    }
    return ret;
}
 
void solution() {
    answer = coverPaper(0, 0, 0);
    answer = (answer == INF) ? -1 : answer;
}
 
int main() {
    //초기화
    N = 10;
    memset(map, 0, sizeof(map));
    memset(covered, false, sizeof(covered));
    memset(cnt, 0, sizeof(cnt));
    answer = 0;
 
    //입력
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
 
    //해법
    solution();
 
    //출력
    cout << answer << "\n";
 
    //종료
    return 0;
}

 

DFS에 대해 알아볼 수 있는 문제였습니다.