백준 17136 색종이 붙이기

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

17136번: 색종이 붙이기

정말 까다로운 문제 중 하나라고 생각합니다. 백트래킹으로 해서 해야 하는 것은 맞는데 첨에 그냥 호기심으로

5 X 5 색종이 부터 5개씩 우선 넣고 넣을 수 있으면 넣고 들어가면 개수 세고 해서 1 X 1까지 해보고

현재 배열에 1이라는 것이 있다면 -1 아니면 세었던 갯수를 출력하는 식으로 했는데 예제는 일단 다 맞았지만

역시 그런 방식은 아닐줄 알았지만 정말 아녔습니다.

 

그래서 심기일전의 마음가짐으로 백트래킹을 사용하여 문제를 풀이를 진행하였습니다.

 

1 X 1부터 넣고 최솟값을 뽑아내면 시간 초과나 더 느리지 않을까 해서 5 X 5부터 넣었고 

일반적인 백트래킹 방식을 적용하였습니다. 하지만 풀이는 일반적인 걸 적용했지만 결과적으로 일반적인 것과

동 떨어진 풀이가 되었습니다. 

그 점 참고하고 읽어주시기 바랍니다.

 

각 종이 1 X 1 //////// 2 X 2 //////// 3 X 3 //////// 4 X 4 //////// 5 X 5 ////////

 

각각 종이마다 5개씩 가집니다. 그래서 

그럴 경우는 없지만 현재 덮는 종이가 넉넉하다면 총 5 X 5 ~ 1 X 1이 나오는 경우가

0 0 0 0 0

1 0 0 0 0

 

...

 

5 5 5 5 5까지 나오는 거라서 정말 잘못하면 너무 깊이가 깊어져서 백트래킹이 불가능 해집니다.

 

그래서 우리는 최대한 이경우를 줄여 가지치기를 잘해야 합니다.

 

 

 

색종이 문제가 약간 백준의 cctv 문제와 순열을 뽑는 백트래킹을 합쳐놓은 것이 아닐까 조심 스레 추측해봅니다.

이랬든 저랬든 풀기만 하면 되는 거 아니겠습니까? 일단 풀어봅시다.

 

저는 일단 탈출 조건을 어떻게 잡을까를 제일 고민을 했습니다. 

탈출 조건이 명확해야 시간초과없이 잘나오기 때문에 제일먼저 탈출 조건을 고민을 합니다.

여기서는 탈출조건이 무엇일까요?

 

색종이가 1을 다 덮었을 때인데 그것을 어떻게 확인을 하지 색종이 개수를 체크하는 것도 맞지도 않고 고민하다가

그냥 이중 포문으로 

검사를 하면서 1이 없다면 flag==0 그대로 일 것이고 그걸 통해 다 덮인 것을 확인했습니다.

 그렇게 해서 최소값을 뽑아 내면 되는거죠

 

여기서 3항연산자를 썼는데 

if( ret > cnt)  ret = cnt;

이것과 별반 차이는 없는데 좀 여러가지 문법을 써보기 위해 사용하였습니다.

편한 방법을 사용하시면 됩니다. #include<algorithm> 헤더파일을 선언해서 ret = min(ret,cnt); 로 하셔도 되구요.

 

탈출조건은 정해졌으니 이제 5개를 순열처럼 0 0 0 0 0 부터 쭉 다 쓰려면 어떻게 해야할까를 먼저 생각했습니다.

cmap은 배열을 복사하기 위해 사용한 배열입니다.

나머지는 각 조건에 5개만 사용할수 있도록 5개 되면 continue가 되어 사이즈가 다른 종이를 덮을수 있게 했습니다.

그렇게 cnt+1해주면서 백트래킹을 진행했습니다.

 

무엇보다 가장 중요한것은 1의 위치 덮을 위치를 찾는것인데 처음에는 위의 소스에 이중포문을 덮어 인덱스 찾고 

그 곳에서 5개짜리 넣어보고 하는식으로 했는데 이게 덮어버리고 종료를 해버려서 잘못됬음을 인지하고 

인덱스를 따로 그냥 찾아서 돌려야겠다 생각이 들었습니다.

위와 같은 소스를 이용하여 색종이를 넣을 위치를 찾았습니다.

그렇게 해서 돌려가면서 넣을수 있는 위치면 map[][[] 이 1이였던것을 처음에 2로 초기화를 했었는데 왠지 모르게

답이 제대로 안나와서 0으로 그냥 변경을 했습니다.

그리고

넣을수 있는 위치를 확인하고 종이를 넣는것을 구현한것으로 위와 같이 구현을 하시면됩니다.

우선 넣을수있으면 가장자리부터 덮는다는 의미로 0으로 바꿔주고 범위를 벗어나거나 혹시나 놓을수 없는

공간이라면 리턴을 시켜주면됩니다.

마지막으로 백트래킹한 부분입니다.

종이가 각각 5개씩이여서 제한을 두고 그 이상인경우 continue를 해주었고 그렇지 않으면 무조건 넣었습니다.

아래 소스를 봐보겠습니다.

넣을수있는 공간에서 부터 넣어봐야지 모든 경우를 넣어 볼수 있기 때문에 위에서 인덱스를 찾고

아래와같이 백트래킹을 함으로써 문제를 해결하였습니다.

#include<stdio.h>
int map[10][10];
int numchk[6];
int ret = 0x7fffffff;
void copy(int cmap[10][10], int map[10][10]) {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            cmap[i][j] = map[i][j];
        }
    }
}
void dfs(int r, int c, int idx, int cnt)
{
    if (cnt > ret) return;// cnt가 ret보다 크면 또 검사하면 오래걸리니 제외
    int flag = 0;
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (map[i][j] == 1) {
                flag = 1;
                break;
            }
            if (flag) break;
        }
    }// 조건 검사
    if (flag == 0) {
        ret = ret > cnt ? cnt : ret;//최소값
 
        return;
    }// 탈출 조건
    for (int i = r; i < r + idx; i++) {
        for (int j = c; j < c + idx; j++) {
            if (i < 10 && j < 10 && map[i][j] == 1) map[i][j] = 0;
            else if (i >= 10 || j >= 10 || map[i][j] == 0)return;
        }
    }
 
 
    int flag1 = 0;
    int i; int j;
    for (i = 0; i < 10; i++) {
        for (j = 0; j < 10; j++) {
            if (map[i][j] == 1) {
                flag1 = 1;
                break;
            }
        }
        if (flag1 == 1) break;
    }// 인덱스 찾기
 
    int cmap[10][10] = { 0, };
    for (int num = 1; num <=5; num++) {
        if (numchk[num] == 5)continue;
        copy(cmap, map);
        numchk[num]++;
        dfs(i, j, num, cnt + 1);
        numchk[num]--;
        copy(map, cmap);
    }
 
}
 
 
int main(void) {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            scanf("%d", &map[i][j]);
 
        }
    }
    dfs(0, 0, 0, 0);
    if (ret == 0x7fffffff)printf("-1\n");
    else printf("%d\n", ret != 0 ? ret - 1 : 0);
    return 0;
}

오랜만에 재귀를 구현하려다 보니 힘이 많이 들었습니다. 하지만 앞으로도 익숙해지기 위해서는 도전을 두려워 하지 

않아야 해서 계속 도전해볼 생각입니다. 

다음번에는 비슷한 문제 14391 종이 조각에 대해서 리뷰해드리겠습니다.

 

그럼 오늘은 여기까지 입니다. 감사합니다.