백준(boj) 14391 - 종이조각

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

👀문제이해 및 풀이방법

전형적인 브루트 포스 문제중 dfs문제이다. 하지만 조금 복잡하다 기본적으로 Q,stack이 아닌 재귀방식의 백트래킹을 사용해야 한다.

한칸씩 넘어가면서 재귀호출 하는 방식이 익숙하지 않다면 힘들것 같다.. 생각보다 시간이 많이 걸렸는데 더 효율적으로 풀 수 있는 방법이 있는지는 모르겠다

오른쪽과 아래쪽을 visit배열에 체크해 두면서 재귀를 돌리면 된다 어렵다기 보다는 복잡하다는게 더 어울리고 익숙해질 필요가 있는 문제유형이라는 생각을 하였다

📝코드

#include <iostream>
#include <vector>
using namespace std;
class paper{
private:
    vector<vector<char>> map;
    vector<vector<bool>> visit;
    int N,M,MAX=0;
public:
    paper(){
        std::cin >> N >> M;
        map.resize(N,vector<char>(M));
        visit.resize(N,vector<bool>(M,false));
        set_val();
        
    }

    void set_val(){
        for(int i=0;i<N;i++)
            for(int j=0;j<M;j++)
                std::cin >> map[i][j];
    }
    
    void dfs(int x,int y,int val){
        if(y==M){
            dfs(x+1,0,val);
            return ;
        }
        else if(x==N){
            MAX=max(MAX,val);
            return ;
        }
        else if(visit[x][y]==true){
            dfs(x,y+1,val);
            return ;
        }
        string str = "";
        for(int cy = y;cy<M;cy++){
            if(visit[x][cy]==true)
                break;
            str+=map[x][cy];
            for(int j=y;j<=cy;j++)
                visit[x][j]=true;
            dfs(x,cy+1,val+stoi(str));
            for(int j=y;j<=cy;j++)
                visit[x][j]=false;

        }
        str = "";
        for(int cx = x ; cx<N;cx++){
            if(visit[cx][y]==true)
                break;
            str+=map[cx][y];
            for(int i=x;i<=cx;i++)
                visit[i][y]=true;
            dfs(x,y+1,val+stoi(str));
            for(int i=x;i<=cx;i++)
                visit[i][y]=false;
        }
        


    }
    void find_sol(){
        dfs(0,0,0);
        std::cout << MAX << "\n";
    }




};
int main(){
    cin.tie(NULL);cout.tie(NULL);
    ios_base::sync_with_stdio(false);
    paper pp;
    pp.find_sol();

    return 0;
}