백준 14391 종이 조각

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

14391번: 종이 조각

이전에 https://3dpit.tistory.com/11?category=791949

백준 17136 색종이 붙이기

색종이 붙이기를 리뷰 하면서 다음에는 종이 조각에 대해서 말씀드리겠다 했던 문제입니다.

이전에 색종이 붙이기를 못 보신 분들은 먼저 색종이 붙이기 보시고 이번장에 들어오셔도 괜찮습니다.

아니더라도 종이 조각하시고 색종이 붙이기 하셔도 괜찮습니다. 

우선 종이 조각은 입력으로 주어지는 정사각형에 숫자가 들어있는데 

위의 7개의 도형을 이용해 전체를 나누었을때 나눈 구역의 숫자의 합이 최대가 되는것을 출력하는 문제입니다.

지금까지 같이 풀어오신분들은 이문제도 백트래킹으로 하면 되겠구나 바로 감이 오실것입니다.

맞습니다. 이문제도 백트래킹을 이용해서 풀수 있습니다.

여기서 포인트는 위의 7개의 도형을 전체 덮고 각 구역을 숫자로 만들어 더해서 최대값을 뽑을수 있는 소스를 구현할수 있는가 입니다. 

 

저의 풀이 방식을 간단히 설명해드리자면 백트래킹을 하는 기본적인 틀에 

재귀로 들어가기전에 배열을 복사를 해놓고 체크 배열에 각 7개에 맞는 도형의 숫자를

입력을 하고 체크배열이 가득찬경우에 각 구역을 숫자로 만들어 더한후 최대값 비교를

진행을 하였습니다.

#include<stdio.h>
int N, M;
int map[5][5];
int mmap[5][5];
int paper[10];
int num[10];
int ten[10] = { 0,1,10,100,1000,10000 };
int chk[5][5];
int paper_idx[10][3] = {
    {0,0},
    {1,1},
    {1,2},
    {2,1},
    {1,3},
    {3,1},
    {1,4},
    {4,1}
};
int idx1 = 0;
int max = 0x80000000;
void copy(int cmap[5][5], int map[5][5]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cmap[i][j] = map[i][j];
        }
    }
}
struct Data {
    int y; int x;
};
int ret = 0;
int check(int y, int x, int idx) {
    int maxnum = 0x80000000;
    maxnum = paper_idx[idx][0] > paper_idx[idx][1] ? paper_idx[idx][0] : paper_idx[idx][1];
    for (int i = y; i < y + paper_idx[idx][0]; i++) {
        for (int j = x; j < x + paper_idx[idx][1]; j++) {
            if (i > N - 1 || j > M - 1 || map[i][j] == 99)return 0;
 
        }
    }
    return 1;
}
void dfs(int y, int x, int idx) {
 
    
    int flag = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] != 99) {
                flag = 1;
                break;
            }
        }
        if (flag)break;
    }
    if (flag == 0) {
        //for (int i = 0; i < N; i++) {
        //    for (int j = 0; j < M; j++) { 
        //        printf("%2d", chk[i][j]);
        //    }
        //    printf("\n");
        //}
        //printf("\n");
 
        ret = 0;
        int c[5][5] = { 0, };
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (c[i][j] == 0) {
                    c[i][j] = 1;
                    int maxnum = paper_idx[chk[i][j]][0] > paper_idx[chk[i][j]][1] ? paper_idx[chk[i][j]][0] : paper_idx[chk[i][j]][1];
 
                    for (int ii = i; ii < i + paper_idx[chk[i][j]][0]; ii++) {
                        for (int jj = j; jj < j + paper_idx[chk[i][j]][1]; jj++) {
                            ret += mmap[ii][jj] * ten[maxnum];
                            c[ii][jj] = 1;
                            maxnum--;
                        }
                    }
                }
            }
        }
        if (max < ret)max = ret;
        return;
    }
    if (idx != 0) {
        if (check(y, x, idx) == 1) {
            for (int i = y; i < y + paper_idx[idx][0]; i++) {
                for (int j = x; j < x + paper_idx[idx][1]; j++) {
                    map[i][j] = 99;
                    chk[i][j] = idx;
                }
            }
        }
        else return;
    }
    int flag1 = 0;
    int i; int j;
    for (i = 0; i < N; i++) {
        for (j = 0; j < M; j++) {
            if (map[i][j] != 99) {
                flag1 = 1;
                break;
            }
        }
        if (flag1)break;
    }
 
    int cmap[5][5] = { 0, };
    int cchk[5][5] = { 0, };
    for (int nn = 1; nn <= 7; nn++) {
        if (num[nn] == N*M) continue;
        //if (check(i, j, idx) == 1) {
            copy(cmap, map);
            copy(cchk, chk);
 
            num[nn]++;
 
            dfs(i, j, nn);
            num[nn]--;
 
            copy(map, cmap);
            copy(chk, cchk);
        }
 
    //}
}
int main(void)
{
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &map[i][j]);
            mmap[i][j] = map[i][j];
        }
    }
    dfs(0, 0, 0);
    printf("%d\n", max);
    return 0;
}