백준 17136번 - 색종이 붙이기

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

DFS를 통해 좌표에서 색종이를 붙일 수 있는지 없는지 확인을 한 뒤에

붙일 수 있다면 재귀호출을 하고 모두 붙였는지를 확인하는 방향으로 문제를 해결했다.

이전에 색종이를 모든 붙인 개수보다 현재 색종이를 붙인 개수가 더 많아지거나

모든 색종이를 붙였을 경우에는 더이상 호출하지 않고 종료시킬 수 있도록 했다.

1과 0이 존재하는 paper 변수를(입력 받은 2차원 배열 종이 공간) 매개변수로 함수를 연속으로 호출해서 시간 초과는 아니지만 오래 걸리는 것 같다.

전역으로 처리하기가 어려워서 이 부분은 좀 더 고민을 하고 코드를 수정해야 할 것 같다.

dfs함수 부분의 주요 로직을 살펴보면

다음 dfs 함수를 호출하기 전에 check변수를 통해 현재 종이에 붙일 수 있는 좌표인 y,x좌표를 구할 수 있도록 했다.

여기서 실수한 부분은 y,x좌표를 구했으면 바로 나와야 하는데 그 지점에서 다시 dfs 함수를 호출해서 무한 루프를 돌았다.

그리고 1~5까지 사용할 수 있는 색종이의 개수가 5개 이기 때문에, 붙이려는 색종이의 개수가 남았는지를 먼저 확인하고 

해당 길이를 붙일 수 있는지 확인 했다.(붙이려는 칸의 범위가 벗어나거나 0이 있는지 확인)

백트래킹을 진행하는 과정에서 잘못 구현해서 무한 루프가 돌았는데

주어진 시간안에 해결하지 못해서 문제 해결 방향을 세우는 연습을 더 해야 할 것 같다...

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
 
int ans=-1;
int color_cnt[6]={0,5,5,5,5,5};
 
bool prove(vector<vector<int>> paper){
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            if(paper[i][j])
                return false;
        }
    }
    return true;
}
 
bool zero_exist(int y,int x,int len,vector<vector<int>> paper){
    
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++){
            if(y+i>=10 || x+j>=10)
                return true;
            
            if(paper[y+i][x+j]==0)
                return true;
        }
    
    return false;
}
 
//0을 1로, 1을 0으로 세팅(색종이 붙이거나, 붙인 색종이 원상복귀 용도)
vector<vector<int>> set_paper(int y,int x,int len,vector<vector<int>> paper){
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            paper[y+i][j+x]=(paper[y+i][j+x])? 0:1;
    
    return paper;
    
}
void dfs(int y,int x,int cnt,vector<vector<int>> paper){
    
    
    if(ans!=-1 && cnt>ans)
        return;
    
    //모두 붙였는지 확인(모두 0인지)
    if(prove(paper)){
        ans=(ans==-1)? cnt:min(ans,cnt);
        return;
    }
    
    
    /*
      1이 존재하는 좌표(y,x) 확인
      3중 for문으로 다시 색종이 붙이는 작업 진행하면 무한 루프돈다.
    */
    bool check=false;
    for(y=0;y<10;y++){
        for(x=0;x<10;x++){
            if(paper[y][x]){
                check=true;
                break;
            }
        }
        if(check)
            break;
    }
    
    for(int len=5; len>0; len--){
        
        //색종이 붙일 수 있는지 확인
        if(color_cnt[len]==0)
            continue;
        
        //붙이려는 색종이 공간에 0이 있거나 범위 벗어나는지 확인
        if(zero_exist(y,x,len,paper))
            continue;
        
        //해당 길이(사이즈)만큼 색종이 사용
        paper=set_paper(y,x,len,paper); //해당 길이만큼 0으로
        color_cnt[len]--;
        dfs(y,x,cnt+1,paper);
        
        paper=set_paper(y,x,len,paper); //해당 길이만큼 1로
        color_cnt[len]++;
        
    }
}
int main(){
    
    vector<vector<int>> paper(10,vector<int>(10,0));
    for(int i=0;i<10;i++)
        for(int j=0;j<10;j++){
            cin>>paper[i][j];
        }
    
    dfs(0,0,0,paper);
    cout<<ans<<endl;
    return 0;
}