[DFS/백트래킹] 백준 17136번 - 색종이 붙이기

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

17136번: 색종이 붙이기

백준 DFS/백트래킹 문제 '색종이 붙이기'문제입니다.

실제로 삼성 A형 모의기출에 출제된 문제이며, 가지치기를 이용한 탐색을 요구하는 문제였습니다.

경사로, 활주로 건설 문제처럼 범위를 고려하며 각 크기의 색종이를 붙일 수 있으면 붙이고 넘어간 뒤 해당하는 탐색을 종료한 뒤에 다시 색종이를 떼주는 작업을 해주는 전형적인 DFS 함수의 틀을 고려해 구현했습니다.

 

상단에는 종료조건에 대한 구현을 해주었으며, 특히 전역 정답보다 현재 정답이 같거나 큰 경우 더이상 탐색을 하지 않도록 하는 가지치기 부분이 시간을 거의 반으로 줄여주는 역할을 하게 하였습니다.

 

아래는 C언어 기반의 코드입니다.

#include <stdio.h>
#pragma warning(disable:4996)
 
#define MAX 10
#define INF 987654321
int remain[6] = { 0, 5, 5, 5, 5, 5 };
int map[MAX][MAX];
int cnt = 0;
int answer = INF;
 
int min(int a, int b){
    if (a < b) return a;
    return b;
}
 
void solve(int r, int c){
    if (answer <= cnt) return;
    if (r >= MAX){
        answer = min(answer, cnt);
        return;
    }
    if (c >= MAX){
        solve(r + 1, 0);
        return;
    }
    if (map[r][c] == 0) {
        solve(r, c + 1);
        return;
    }
    for (int len = 5; len >= 1; len--){
        if (remain[len] == 0 || r + len > MAX || c + len > MAX){
            continue;
        }
        int flag = 1;
        for (int i = r; i <= r + len - 1; i++){
            for (int j = c; j <= c + len - 1; j++){
                if (map[i][j] == 0) {
                    flag = -1;
                    break;
                }
            }
            if (flag == -1) break;
        }
 
        if (flag == -1) continue;
 
        for (int i = r; i <= r + len - 1; i++){
            for (int j = c; j <= c + len - 1; j++){
                map[i][j] = 0;
            }
        }
        remain[len]--;
        cnt++;
 
        solve(r, c + len);
 
        for (int i = r; i <= r + len - 1; i++){
            for (int j = c; j <= c + len - 1; j++){
                map[i][j] = 1;
            }
        }
 
        remain[len]++;
        cnt--;
    }
}
 
int main(){
    for (int r = 0; r < 10; r++){
        for (int c = 0; c < 10; c++){
            scanf("%d", &map[r][c]);
        }
    }
    solve(0, 0);
    if (answer == INF)
        printf("-1\n");
    else
        printf("%d\n", answer);
    return 0;
}