백준 17136번 : 색종이 붙이기

문제 링크 : https://www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

 문제 설명 

 

1. 10 x 10 배열에 0,1로 가득차있는데 1이 적힌 칸을 모두 색종이로 덮어야함 .

2. 색종이의 크기는 5 x 5 , 4 x 4 ,3 x 3 ,2 x 2 , 1 x 1이 각각 5장씩 있음.

3. 색종이로 덮을때 0인부분은 덮으면 안된다. 가능한 경우의 색종이 사용량 최소값을 출력.

 

 

 알고리즘 

 

1. (0,0) 부터 (9,9) 까지 1을찾는다 .

2. 1을 발견하면 크기가 큰것부터 덮어본다

3. 가능하면 덮고 백트래킹 진행.

4. 배열의 마지막 까지 확인했을경우 총 사용한 종이의 갯수를 갱신한다

5. 만약 종이의 갯수가 한번도 갱신 되지 않았다면 -1을 출력.

 

 

 코드 

 

#include<iostream>
#include<algorithm>
using namespace std;
int arr[10][10];
int num[6] = { 0,5,5,5,5,5 };
int result = 101;
 
//종이 붙일수있는지 판단하는 함수.
bool possible(int y, int x, int n) {
 
    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
            if (arr[i][j] != 1)return false;
        }
    }
    return true;
}
 
void Fill(int y, int x, int n, int num) {
    for (int i = y; i < y + n; i++) {
        for (int j = x; j < x + n; j++) {
            arr[i][j] = num;
        }
    }
}
 
void func(int y, int x, int cnt) {
    {//가로 탐색이 끝났으면 세로탐색 시작
    if (x == 10){
        func(y + 1, 0, cnt);
        return;
    }
    //세로 탐색이 끝났으면 최소값 갱신
    if (y == 10) {
        result = min(result, cnt);
        return;
    }
    //0 이면 확인할 필요 x
    if (arr[y][x] == 0) {
        func(y, x + 1, cnt);
        return;
    }
    //크기가 5까지 잇으므로 5부터 1까지
    for (int i = 5; i > 0; i--) {
        //범위 초과 , 갯수 초과
        if (x + i > 10 || y + i > 10 || num[i] == 0) continue;// 
        //종이를 붙일수있으면 .
        if (possible(y, x, i)) {
            Fill(y, x, i, 0);//붙이고
            num[i]--;//종이 사용
            func(y, x, cnt + 1);//종이 갯수 ++
            num[i]++;//종이 복구
            Fill(y, x, i, 1);//떼고
        }
 
 
    }
 
}
 
 
 
int main() {
 
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cin >> arr[i][j];
        }
    }
    func(0, 0, 0);
    if (result == 101) cout << -1;
    else cout << result;
}

 

 

참고한 블로그 : https://jaimemin.tistory.com/1249

 

 

재귀함수 구현에서 너무 헷갈려서 다른 블로그를 참고하였다. 

저기블로그에 좋은 풀이가 많다.