#17136번 색종이 붙이기 (C++)

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

17136번: 색종이 붙이기

먼저 이 문제의 유형이 Brute Force임을 기억하자.

즉, 모든 가짓수를 고려해서 하나하나 테스트 해봐야한다는 뜻이다.

만약 2*2 색종이가 딱 들어 맞는다해도, 다른 영역에서 4*4를 써서 해당 영역을 더는게 효과적이다면 2*2가 아닌 1*1을 활용하는 것이 정답일 수도 있다. 때문에 모든 가짓수를 고려해야하는데, 이 점을 간과해서 나는 테스트 케이스 7번에서 실패하고 말았다. 

파랑색을 2*2로 덮지 말고 빨간색을 4*4로 덮어야한다.

잘못 작성했던 코드에서는 1부터 시작해서 5까지 색종이의 크기를 고려하여

해당 크기의 색종이로 덮을 수 있으면 다음 크기의 색종이로 넘어가는 코드였다.

문제는 그렇게 하고 끝을 냈다는 사실이다. 무조건 덮었다고 정답이 아니라, 다른 가능성또한 고려해야한다.

그러기 때문에 Brute Force에서는 bool문을 활용(혹은 다른 형태도 활용가능)해서 방문했던 영역을 체크하고 다른 가능성을 파악하고자 방문 영역을 다시 해제하는, 즉, 되돌리는 과정이 중요하다. 

 

<실패했던 코드>

#include <iostream>
using namespace std;

int arr[11][11] = {0,}, ans = 0, paper[6]={0,5,5,5,5,5}, total = 0;
bool ch[11][11] = {false,};
void go(int y, int x, int num){
    if(ch[y][x]) return;
    if(num>=5){ // 제일 큰걸로 처리 가능
        paper[5]--;
        return;
    }
    int temp = num*num;
    ch[y][x] = true;
    for(int i=0; i<=num; i++){
        for(int j=0; j<=num; j++){
            if(i==0&&j==0) continue;
            if(arr[y+i][x+j]==1&&!ch[y+i][x+j]) {temp++; ch[y+i][x+j] = true;}
        }
    }
    if(temp==(num+1)*(num+1)) {
        ch[y][x] = false;
        go(y,x,num+1);
    }
    else{
        paper[num]--;
        paper[1] -= temp-((num)*(num));
        return;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i=1; i<=10; i++){
        for(int j=1; j<=10; j++){
            cin >> arr[i][j];
            if(arr[i][j]==1) total++;
        }
    } 
    if(total==0) {cout << 0 << "\n"; return 0;}
    for(int i=1; i<=10; i++){
        for(int j=1; j<=10; j++){
            if(arr[i][j]==1){
                go(i,j,1);
            }
        }
    }
    for(int i=1; i<=5; i++) {
        if(paper[i]<0) {ans = -1; break;}
        ans += 5-paper[i];
    }
    cout << ans << "\n";
    return 0;
}

보시다시피 위 코드에서는 덮어버리고 끝내고, 다른 색종이로 덮을 수 있는 가능성을 고려하기위해 되돌아가는 과정이 없다.

 

<정답 코드>

#include <iostream>
const int MAX = 11;
using namespace std;

int arr[MAX][MAX] = {0,}, ans = 1e4, cnt = 0, paper[6]={0,5,5,5,5,5};
void go (int y, int x){
   if(x==MAX){
       go(y+1,1); // 다음줄 진행
   }
   if(y==MAX){
       ans = min(ans,cnt); // 마지막 줄 까지 끝냈으면 최소값으로 답을 정하기
       return;
   }
   if(arr[y][x]==0) go(y,x+1);
   for(int i=5; i>=1; i--){
       if(paper[i]==0||y+i>MAX||x+i>MAX) continue; // 종이를 다 썻거나 종이를 덮었을때 범위를 넘어가면 다음 종이로 패스하기
       bool ch = false;
       for(int j=0; j<i; j++){
           for(int k=0; k<i; k++){
               if(arr[y+j][x+k]==0){
                   ch = true;
                   break;
               }
           }
           if(ch) break;
       }
       if(ch) continue; // 덮을수 없다는 뜻이니 다음 종이로 패스
       for(int j=0; j<i; j++){ // 덮었다고 가정하기
           for(int k=0; k<i; k++){
               arr[y+j][x+k] = 0;
           }
       }
       paper[i]--;
       cnt++;
       go(y,x+i); // 덮은 영역만큼 건너뛰고 다음 영역으로 넘어가기
       for(int j=0; j<i; j++){
           for(int k=0; k<i; k++){
               arr[y+j][x+k] = 1; // 덮었던 종이 치우기
           }
       }
       paper[i]++;
       cnt--;
   }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    for(int i=1; i<MAX; i++){
        for(int j=1; j<MAX; j++){
            cin >> arr[i][j];
        }
    } 
    go(1,1);
    if(ans==1e4) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}