[백준 14391] 종이 조각 (C++)

14391번: 종이 조각

백트래킹, 브루트 포스

---

 

[백준 1799] 비숍 C++

[백준 17136] 색종이 붙이기 C++

 

위 두 문제들이랑 결이 비슷하다. 특히 비숍

 

현재 열이 M에 도달하면 다음 행, 0번 열으로 이동하는 방식과 현재 칸에 비숍을 놓을지 말지를 결정하기 위해 사용한 대각선 배열의 느낌이 비슷하다.

 

각각의 칸에 O를 넣을지 X를 넣을지 정해보자

O가 들어간 칸들은 가로로 더해주고, X가 들어간 칸들은 세로로 더해준다.

이렇게 모든 칸을 o, x 작업을 마치고 가로와 세로의 연속된 숫자들을 잘 더해주면 현재 트래킹 상태에서의 합을 구할 수 있다. 이렇게 최대 2^16번 구하면 최대값을 구할 수 있다.

 

처음에 가로, 세로를 구분하고 1x1칸도 생각해줘야 하나 했지만 어차피 1x1은 가로 세로에 포함될 수 있기 때문에 신경쓸 필요가 없다고 생각했다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define fasti ios_base::sync_with_stdio(false); cin.tie(0);
#define fastio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 1e9+7
#define pii pair<int, int>
 
typedef long long ll;
// typedef pair<int, int> pii;
 
using namespace std;
 
int N, M;
int Map[5][5];
bool visited[5][5];
int ans;
 
void input(){
    cin >> N >> M;
    string str;
    for(int r = 0; r < N; r++){
        cin >> str;
        for(int c = 0; c < M; c++){
            Map[r][c] = str[c] - '0';
        }
    }
}
 
void dfs(int r, int c){
    if(r == 4){
        int sum = 0;
        for(int r = 0; r < N; r++){
            int temp = 0;
            for(int c = 0; c < M; c++){
                if(visited[r][c]) temp = temp*10 + Map[r][c];
                else{
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp;
        }
        for(int c = 0; c < M; c++){
            int temp = 0;
            for(int r = 0; r < N; r++){
                if(!visited[r][c]) temp = temp*10 + Map[r][c];
                else{
                    sum += temp;
                    temp = 0;
                }
            }
            sum += temp;
        }
        ans = max(ans, sum);
        return;
    }
    if(c == 4){
        dfs(r+1, 0);
        return;
    }
    visited[r][c] = true;
    // 가로로 이어짐
    dfs(r, c+1);
    
    visited[r][c] = false;
    // 세로로 이어짐
    dfs(r, c+1);
}
 
void solve(){
    dfs(0, 0);
    cout << ans << "\n";
}
 
int main(){
    input();
    solve();
    
    return 0;
}