BOJ 17136 - 색종이 붙이기

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

 

이 문제는 백트래킹을 써야 풀 수 있는 문제이다.

 

먼저 10 * 10 크기의 이차원 배열을 (0, 0) 부터 하나씩 순회하면서, 값이 1인 부분을 찾아내고,

값이 1인 (i, j) 좌표에 5개의 색종이 중 어떤 것을 붙일 수 있는지 판별한다

어떤 k 번째 색종이를 붙일 수 있다면, 그 색종이를 붙이고 다음 가지수를 찾기 위해 백트래킹을 써준다.

 

이때 순회를 하기 위한 재귀함수의 종료조건은 

1. 10 * 10 크기의 이차원 배열의 크기를 벗어날때

2. 사용한 색종이의 갯수 cnt 가 answer 보다 커질때 (최소갯수의 색종이를 쓰기 위해서임)

3. 열의 최대 크기를 벗어났을때, 다음 행으로 넘어간다

가 된다.

 

- c++

#include <iostream>
 
#define INF 987654321
 
using namespace std;
 
int answer = INF;
int papers[5] = {5, 5, 5, 5, 5};
int adj[10][10];
 
bool can_cover_paper(int r, int c, int k) {  
    for (int i = r; i <= r + k; ++i) 
        for (int j = c; j <= c + k; ++j) 
            if (i < 0 || i >= 10 || j < 0 || j >= 10 || adj[i][j] == 0)
                return false;
    return true;
}
 
void attach_paper(int r, int c, int k, bool can_cover) {
    for (int i = r; i <= r + k; ++i)
        for (int j = c; j <= c + k; ++j)
            adj[i][j] = can_cover;
}
 
void recursion(int r, int c, int cnt) { // y, x, 붙인갯수 
    if (r >= 9 && c > 9) {
        answer = min(answer, cnt);
        return;
    }
    
    if (answer <= cnt) return;
    
    if (c > 9) {
        recursion(r + 1, 0, cnt);
        return;
    }
    
    if (adj[r][c] == 1) {
        for (int k = 4; k >= 0; --k) {
            if (papers[k] > 0 && can_cover_paper(r, c, k)) {
                attach_paper(r, c, k, 0);
                papers[k]--;
                recursion(r, c + 1, cnt + 1);
                attach_paper(r, c, k, 1);
                papers[k]++;
            }    
        }
    } else {
        recursion(r, c + 1, cnt);
    }
} 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    for (int i = 0; i < 10; ++i)
        for(int j = 0; j < 10; ++j)
            cin >> adj[i][j];
            
    recursion(0, 0, 0);
    
    if (answer == INF) answer = -1;
    cout << answer;
        
    return 0;
}