백준(boj) 17136 - 색종이 붙이기

문제 링크 - https://www.acmicpc.net/problem/17136

👀문제이해 및 풀이방법

너무고생을 한 문제이다. 결국 몇번을 시도하다가 찾아보고 풀었다 최근 브루트 포스 문제만 잔뜩 풀고있는데 쉬워보이지만 완전탐색을 어떤 방식으로 해야할지 너무 헷갈리는 문제이다. dfs를 사용한 백트래킹이라는 방향은 잘 접근하였지만 map전체를 계속해서 탐색하면서 가능한 부분을 지워나가는 식으로하여 만일 다 지워진 경우 답을 업데이트 하는 방식을 사용하였다. 뭐가 문제인지 모르겠지만 계속 통과가 안되었고 몇시간을 고민했는지 모르겠다. 한번 잘못된 방향으로 시작하면 되돌리기가 정말 어려운것 같다 5가지의 색종이 경우에 대해서 맵 전체를 훑으며 가능한 부분을 하나씩 채워가는 방식이 좋다고 생각하였고 결국 찾아보기 전까지 풀지 못했다.
답은 내 생각과 딱 반대로 맵 전체를 탐색하면서 각 지점에서 5가지의 색종이로 가능한지를 탐색하며 맵을 하나씩 넘어가는 방식이였다. 꼭 다시 풀어봐야할 문제이다 말로 설명하기가 정말 어렵다.

📝코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int INF=1000000000;
class colorpaper{
private:
    vector<vector<int>> map;
    vector<int> avaliable;
    int N=10,sol=INF;
public:
    colorpaper(){
        map.resize(N,vector<int>(N));
        avaliable.resize(5,5);
        set_val();
    }
    void set_val(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                std::cin >> map[i][j];
            }
        }
    }
    bool check(int x,int y,int d){
        for(int i=x;i<x+d;i++){
            for(int j=y;j<y+d;j++){
                if(map[i][j]==0){
                    return false;
                }
            }
        }
        for(int i=x;i<x+d;i++){
            for(int j=y;j<y+d;j++){
                map[i][j]=0;
            }
        }
        return true;

    }
    void checkout(int x,int y,int d){
        for(int i=x;i<x+d;i++)
            for(int j=y;j<y+d;j++)
                map[i][j]=1;
    }
    void dfs(int x,int y,int result){
        if(y==N){
            dfs(x+1,0,result);
            return ;
        }
        if(x==N){
            sol=min(sol,result);
            return ;
        }
        if(map[x][y]==0){
            dfs(x,y+1,result);
            return ;
        }
        for(int i=0;i<5;i++){
            if(avaliable[i] && x+i<N && y+i<N){
                if(check(x,y,i+1)){
                    avaliable[i]--;
                    dfs(x,y+i+1,result+1);
                    avaliable[i]++;
                    checkout(x,y,i+1);
                }
            }
        }
    }
    void find_sol(){
        dfs(0,0,0);
        if(sol==INF)
            std::cout << -1 << '\n';
        else
            std::cout << sol << '\n';
    }

};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    colorpaper cp;
    cp.find_sol();
    return 0;
}