✅ DFS ✅ 백트래킹

문제

1. 해결 로직

색종이가 큰 것부터 붙이면 색종이를 최소 개수만 사용할 수 있지 않을까 생각하기 쉽지만 꼭 그렇지는 않다. 예를 들어 6x6를 붙인다고 했을때 가장 큰 5x5 부터 붙이면 5x5 1개, 1x1 11 개, 총 12개가 필요하다. 하지만 3x3을 사용하면 4개만 사용하고도 다 붙일 수 있다.
따라서 가능한 모든 색종이를 재귀적으로 붙여 최소 개수를 구해야 한다.
DFS

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int map[11][11];
int paper[6]; // 사용한 색종이 수 카운트
int ans = 26;

bool is_possible(int y, int x, int size){
    if(paper[size]==5) return false;
    if(y+size>11 || x+size>11) return false; // 12부터 안되는 거 - 주의

    for(int i=y;i<y+size;i++){
        for(int j=x;j<x+size;j++){
            if(map[i][j]==0) return false;
        }
    }

    return true;
}

void DFS(int y, int x){
    if(x==11){ // x로 끝까지 갔으므로 아래줄 맨 외쪽부터 다시 탐색
        DFS(y+1,0);
        return;
    }
    if(y==11){ // x:11, y:10에서 넘어옴 => 끝까지 도달
        int total_paper = 0;
        for(int i = 1;i<=5;i++){
            total_paper += paper[i];
        }

        ans = min(ans, total_paper);
        return;
    }
    if(map[y][x]==0) { // 붙일 수 없는 칸이므로 다음 오른쪽 칸으로 이동
        DFS(y,x+1);
        return;
    }

    for(int size = 1;size<=5;size++){
        if(is_possible(y,x,size)){ // ixi로 붙일 수 있는 크기인지 판단
            // 1. 색종이 붙임 (붙인 곳은 다음에 또 붙일 수 없으므로 0으로 만들어주면됨)
            for(int j=y;j<y+size;j++){
                for(int k=x;k<x+size;k++){
                    map[j][k] = 0;
                }
            }
            paper[size] ++; // 2. 붙인 색종이 카운트

            DFS(y, x+1); // 3. 다음 오른쪽 칸으로 이동

            // 초기화
            for(int j=y;j<y+size;j++){
                for(int k=x;k<x+size;k++){
                    map[j][k] = 1;
                }
            }
            paper[size] --;
        }
    }
}

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

    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            cin >> map[i][j];
        }
    }

    DFS(0,0);

    if(ans <= 25) cout << ans << "\n";
    else cout << "-1" << "\n";
    

    return 0;
}

3. 시간 복잡도

모든 좌표에 5가지 색종이를 모두 붙여보므로
O(100^5)이지만,
불가능한 색종이는 붙이지 않기 때문에 (백트래킹) 이것보단 훨씬 적은 시간 복잡도가 나올 것이다.

4. Review

• 색종이를 큰 것부터 붙이는게 아니라 전부 붙여봐야 한다는게 중요했다.
• 각 좌표에 붙일 수 있는 종이인지 아닌지 판별할 때 범위를 조심해야 한다.

if(y+size>11 || x+size>11) return false; // 12부터 안되는 거 - 주의