[C] 백준 17136번 : 색종이 붙이기

문제

 

<그림 1>과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다.

<그림 1>

색종이를 크기가 10×10인 종이 위에 붙이려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다. 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐도 안 된다. 또, 칸의 경계와 일치하게 붙여야 한다. 0이 적힌 칸에는 색종이가 있으면 안 된다.

종이가 주어졌을 때, 1이 적힌 모든 칸을 붙이는데 필요한 색종이의 최소 개수를 구해보자.

 

입력

 

총 10개의 줄에 종이의 각 칸에 적힌 수가 주어진다.

 

출력

 

모든 1을 덮는데 필요한 색종이의 최소 개수를 출력한다. 1을 모두 덮는 것이 불가능한 경우에는 -1을 출력한다.

 

풀이

 

#include <stdio.h>
 
int board[11][11];
int ans = 30;
int paper_cnt[6] = {0,};
 
bool check(int x, int y, int size){
    for(int i = y ; i < y+size ; i++){
        for(int j = x ; j < x+size ; j++){
            if(i>10) return false;
            if(j>10) return false;
            if(board[j][i]!=0) return false;
        }
    }
    return true;
}
 
void attach_or_detach(int x, int y, int size, int f){
    for(int i = y ; i < y+size ; i++){
        for(int j = x ; j < x+size ; j++){
            board[j][i]=f?0:size;
        }
    }
}
 
void DFS(int x, int y, int cnt){
    if(cnt>ans) return;
    while(true){
        if(y==11){
            y = 1;
            x++;
            if(x==11) {
                if(ans>cnt) ans = cnt;
                break;
            }
        }
        if(board[x][y]==0) break;
        y++;
    }
    for(int i = 5 ; i >= 1 ; i--){
        if(check(x,y,i)){
            if(paper_cnt[i]<5){
                attach_or_detach(x,y,i,0); // attach
                paper_cnt[i]++;
                DFS(x,y+i,cnt+1);
                paper_cnt[i]--;
                attach_or_detach(x,y,i,1); //detach
            }
        }
    }
}
 
int main(){
    for(int i = 1 ; i <= 10 ; i++){
        for(int j = 1 ; j <= 10 ; j++){// -1 : do not fill, 0 : have to fill
            scanf("%d",&board[i][j]);
            board[i][j]--;
        }
    }
    DFS(1,1,0);
    if(ans==30) printf("-1\n");
    else printf("%d\n",ans);
}

 

쉬워 보여서 풀었다가 개고생한 삼성 코테 기출 문제...

알고보니 처음에 틀려서 어디서 틀린지 찾다가 디버깅하는 과정에서 print 문을 너무 많이 써서 이미 맞았는데도 시간 초과가 날 것이라고 지레짐작해서 생긴 문제였다

출력 부분만 지워보니 바로 패스ㅜㅜㅜ

 

DFS로 색종이를 붙일 수 있는 모든 경우를 살펴보았다

이 때 기존에 있는 최소값보다 이미 사용한 색종이의 수가 많은 경우는 더 확인하지 않고 가지치기를 해주었다

입력이 크지 않아서 그런가 백트래킹을 사용하지 않아도 통과였고 시간 차이도 별로 나지 않았다

 

(1,1)부터 시작하여 while문에서 색종이를 붙여주어야 할 좌표를 찾았다

만약 (10,10)까지 간다면 지금까지 사용한 색종이의 개수를 확인하여 최소값 보다 작다면 최소값을 갱신시켜주었다

 

색종이를 붙여주어야 할 좌표를 찾았다면 이제 1부터 5까지 크기를 가진 색종이를 붙일 수 있는지 check 함수를 통해 확인해주었다

check 함수는 좌표의 위치와 크기를 받아 받은 좌표를 왼쪽 위 값으로 하여 색종이를 붙일 수 있는지 return 해주는 함수이다

색종이를 붙일 수 있다면 이미 그 색종이를 5번 썼는지 확인하고 5번 미만이라 붙일 수 있다면 attach_or_detach 함수를 통해 색종이를 붙여주었다

attach 할 때는 f에 0을 detach 할 때는 1을 넣어주었다

붙일 때는 그냥 1이나 정한 값을 board에 저장해주어도 되지만 디버깅 과정에서 헷갈려서 색종이의 크기를 저장해주었다

이 과정 때문에 0이 적힌 칸을 색종이를 붙여주어야 하는 칸 -1이 적힌 칸을 색종이가 있으면 안되는 칸으로 지정하기 위해 보드를 입력받은 후 1씩 빼주었다

 

이러한 함수들을 사용해서 모든 경우를 확인해주어 최소값을 출력해주었다