[백준/C++] 17136번: 색종이 붙이기(G2)

문제

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

17136번: 색종이 붙이기

 

 

사용한 알고리즘

2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹

-> 백트래킹.
    모든 경우를 따지지 않고 가지치기하는 문제

 

풀이

1. 5x5색종이부터 1x1색종이까지 차례대로 붙어본다.
2. 붙일 수 있다면(범위가 10x10이내, 사용횟수 use값이 5 이내) 색종이를 붙인 후 재귀함수로 들어간다.
   색종이를 붙일때는 matrix 값을 0으로 바꾸고 use값을 1 증가시킨다.
   재귀함수 탈출 후에는 원래상태로 복구시켜주기위해 matrix값을 1로 바꾸고 use값을 1 감소 시킨다.
3. 1인곳에 색종이를 전부 붙여서 matrix가 전부 0이되면 ans를 갱신해준다. (최솟값을 구하기 위해)

 

소스코드 1

#include <iostream>

using namespace std;
int mat[10][10]; //입력받은거
int use[6]; //use[1]=1x1 ... use[5]=5x5 색종이 사용 개수
int ans=100; //정답 조합들 중에 최솟값을 출력해야함

void solve(){
    int fin=1,x=0,y=0;
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            if(mat[i][j]==1){
                fin=0;
                x=i, y=j;
                break;
            }
        }
        if(!fin) break;
    }

    if(fin){ //mat가 전부 0이면 종료
        int sum=0;
        for(int i=1; i<=5; i++) sum+=use[i];
        ans=min(ans,sum);
        return;
    }
/*
     else if(fin==0)이면 x,y에는 1이 처음나온곳의 행렬 인덱스를 담고있음

     mat[x][y] 를 좌상단으로 해서 5x5 ... 1x1 색종이를 붙여보자
     10x10 범위 벗어나면 안됨
     재귀 갔다오면 상태 되돌려놓기. (mat 1로, use갯수--)
*/

    for(int k=5; k>=1; k--) {
        //// k=5 일때
        //// mat[x][y]가 좌상단인 5x5가 전부 1이라면...
        if (x + k <= 10 && y + k <= 10) {
            int ck = 1;
            for (int i = x; i < x + k; i++) {
                for (int j = y; j < y + k; j++) {
                    if (mat[i][j] == 0) {
                        ck = 0;
                        break;
                    }
                }
            }
            // mat 0으로 바꾸고 use[5]++하고 재귀함수 들어가고, 나와서 다시 mat랑 use[5] 복귀
            if (ck && use[k] < 5) {
                for (int i = x; i < x + k; i++) {
                    for (int j = y; j < y + k; j++) {
                        mat[i][j] = 0;
                    }
                }
                use[k]++;
                solve();
                for (int i = x; i < x + k; i++) {
                    for (int j = y; j < y + k; j++) {
                        mat[i][j] = 1;
                    }
                }
                use[k]--;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            cin>>mat[i][j];
        }
    }
    solve();
    if(ans!=100) cout<<ans;
    else cout<<-1;
    return 0;
}

 

소스코드1이 이해하기 어렵다면 소스코드2로 먼저 이해해보자.
소스코드 2의 if문 5개를 for문으로 간략화시킨게 소스코드 1이다.

 

소스코드 2

#include <iostream>

using namespace std;
int mat[10][10]; //입력받은거
int one, two, three, four ,five; //1x1 ... 5x5 색종이 사용 개수
int ans=100; //정답 조합들 중에 최솟값을 출력해야함

void solve(){
    int fin=1,x=0,y=0;
    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            if(mat[i][j]==1){
                fin=0;
                x=i, y=j;
                break;
            }
        }
        if(!fin) break;
    }

    if(fin){ //mat가 전부 0이면 종료
        ans=min(ans,one+two+three+four+five);
        return;
    }
    
/*
     else if(fin==0)이면 x,y에는 1이 처음나온곳의 행렬 인덱스를 담고있음

     mat[x][y] 를 좌상단으로 해서 5x5 ... 1x1 색종이를 붙여보자
     10x10 범위 벗어나면 안됨
     재귀 갔다오면 상태 되돌려놓기. (mat 1로, one tow... 갯수--)
*/

    //// mat[x][y]가 좌상단인 5x5가 전부 1이라면...
    if(x+5<=10 && y+5<=10){
        int ck=1;
        for(int i=x; i<x+5; i++){
            for(int j=y; j<y+5; j++){
                if(mat[i][j]==0){
                    ck=0;
                    break;
                }
            }
        }
        // mat 0으로 바꾸고 five++하고 재귀함수 들어가고, 나와서 다시 mat랑 five 복귀
        if(ck && five<5){
            for(int i=x; i<x+5; i++){
                for(int j=y; j<y+5; j++){
                    mat[i][j]=0;
                }
            }
            five++;
            solve();
            for(int i=x; i<x+5; i++){
                for(int j=y; j<y+5; j++){
                    mat[i][j]=1;
                }
            }
            five--;
        }
    }

    //// mat[x][y]가 좌상단인 4x4가 전부 1이라면...
    if(x+4<=10 && y+4<=10){
        int ck=1;
        for(int i=x; i<x+4; i++){
            for(int j=y; j<y+4; j++){
                if(mat[i][j]==0){
                    ck=0;
                    break;
                }
            }
        }
        // mat 0으로 바꾸고 four++하고 재귀함수 들어가고, 나와서 다시 mat랑 four 복귀
        if(ck && four<5){
            for(int i=x; i<x+4; i++){
                for(int j=y; j<y+4; j++){
                    mat[i][j]=0;
                }
            }
            four++;
            solve();
            for(int i=x; i<x+4; i++){
                for(int j=y; j<y+4; j++){
                    mat[i][j]=1;
                }
            }
            four--;
        }
    }

    //// mat[x][y]가 좌상단인 3x3가 전부 1이라면...
    if(x+3<=10 && y+3<=10){
        int ck=1;
        for(int i=x; i<x+3; i++){
            for(int j=y; j<y+3; j++){
                if(mat[i][j]==0){
                    ck=0;
                    break;
                }
            }
        }
        // mat 0으로 바꾸고 three++하고 재귀함수 들어가고, 나와서 다시 mat랑 three 복귀
        if(ck && three<5){
            for(int i=x; i<x+3; i++){
                for(int j=y; j<y+3; j++){
                    mat[i][j]=0;
                }
            }
            three++;
            solve();
            for(int i=x; i<x+3; i++){
                for(int j=y; j<y+3; j++){
                    mat[i][j]=1;
                }
            }
            three--;
        }
    }

    //// mat[x][y]가 좌상단인 2x2가 전부 1이라면...
    if(x+2<=10 && y+2<=10){
        int ck=1;
        for(int i=x; i<x+2; i++){
            for(int j=y; j<y+2; j++){
                if(mat[i][j]==0){
                    ck=0;
                    break;
                }
            }
        }
        // mat 0으로 바꾸고 two++하고 재귀함수 들어가고, 나와서 다시 mat랑 two 복귀
        if(ck && two<5){
            for(int i=x; i<x+2; i++){
                for(int j=y; j<y+2; j++){
                    mat[i][j]=0;
                }
            }
            two++;
            solve();
            for(int i=x; i<x+2; i++){
                for(int j=y; j<y+2; j++){
                    mat[i][j]=1;
                }
            }
            two--;
        }
    }

    //// mat[x][y]가 좌상단인 1x1가 1이라면...
    if(x+1<=10 && y+1<=10){
        int ck=1;
        for(int i=x; i<x+1; i++){
            for(int j=y; j<y+1; j++){
                if(mat[i][j]==0){
                    ck=0;
                    break;
                }
            }
        }
        // mat 0으로 바꾸고 one++하고 재귀함수 들어가고, 나와서 다시 mat랑 one 복귀
        if(ck && one<5){
            for(int i=x; i<x+1; i++){
                for(int j=y; j<y+1; j++){
                    mat[i][j]=0;
                }
            }
            one++;
            solve();
            for(int i=x; i<x+1; i++){
                for(int j=y; j<y+1; j++){
                    mat[i][j]=1;
                }
            }
            one--;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    for(int i=0; i<10; i++){
        for(int j=0; j<10; j++){
            cin>>mat[i][j];
        }
    }
    solve();
    if(ans!=100) cout<<ans;
    else cout<<-1;
    return 0;
}