[백준/c++]14391번 종이조각 비트마스킹 풀이

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

14391번: 종이 조각

 

접근 방법

비트 마스킹과 완전 탐색 방법으로 문제를 풀었습니다.
생소했던 비트 마스킹을 2차원 배열에 적용시키는 것이 어려웠습니다.

비트 마스킹을 사용한 이유

이런 입력이 주어지고, 종이를 초록색 상자와 같이 잘랐다고 가정합시다. 그러면 이러한 상황에서 답은

12 + 4 + 5 + 36 = 57입니다.

이렇게 종이 조각이 가로와 세로로 연결되는 모든 조합을 찾기 위해선 비트 마스킹을 활용할 수 있습니다.
비트 마스킹에서,
0은 가로로 연결, 1은 세로로 연결한다고 하겠습니다.
그럼 위의 비트마스킹은 다음과 같이 표현할 수 있습니다.

0으로 연결된 가로줄이 연결되고, 1로 연결된 세로줄이 연결된다. 모든 경우를 연결하고 sum을 구하면 답을 알아낼 수 있을 것입니다. 위에서 보실 수 있듯이, 두번째 줄에 1 - 0 같은 부분은 끊어지는 부분으로, 각 자리가 연결되지 않고 한자리 그 자체로 들어갑니다.

2차원 비트마스킹

요 부분을 많이 고민했으나, 의외로 구하기에는 편했습니다.

3*3 배열이 있고, 각 자릿수의 숫자를 다음과 같이 넣어줍니다.

우리는 각 자리의 숫자를 원본 2차원 배열의 row, col과 연결시켜야합니다. 즉, 위 그림에서 '5'번 자리는 원본 배열의 [1, 3]위치여야 한다는 것이죠. 아 이거 뭔가 수업시간에서 배웠던 것 같은데.... 까먹어서 다음과 같은 식을 머리 깨져가면서 찾았습니다.

그럼 이제 비트마스킹을 적용시켜봅시다.

for(int i=0; i < (1<<(n*m)); i++){
        int mask[5][5]={0, };
        for(int j=0; j<(n*m); j++){
            if(i&(1<<j)){
//                cout<<"found: "<<j<<endl;
                int row = j/m;
                int col = j - (row*m);
//                cout<<j<<" is AT {"<<row<<", "<<col<<")"<<endl;
                mask[row][col] = 1;
            }
            cnt++;
        }
        
//        for(int i=0; i<n; i++){
//            for(int j=0; j<m; j++) cout<<mask[i][j]<<" ";
//            cout<<endl;
//        }
        
        int temp = local_result(mask);
//        cout<<"Local Ans : "<<temp<<"\n==============\n";
        ans = max(ans, temp);
    }

주석 처리 부분을 복구하여 돌려보시면 코드 이해가 간편해지실 거에요.
비트 마스킹에서 1로 처리된 index를 mask에서 1로 처리하고, mask기준으로 잘린 종이로 결과를 구하는 코드입니다.

전체 코드

전체 코드는 다음과 같습니다.

//
//  종이 조각.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2023/01/01.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

char field[5][5];
int n, m;
int local_result(int mask[5][5]){
    bool visited[5][5] = {0, };
    vector<int> v;
    int sum=0;
    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            string temp;
            if(mask[i][j] == 0){
                //가로 탐색
                for(int k=j; k<m; k++){
                    if(mask[i][k] == 0 && visited[i][k] == 0){
                        temp += field[i][k];
                        visited[i][k] = 1;
                    }
                    else break;
                }
            }
            if(mask[i][j] == 1){
                //세로로 연결
                for(int k=i; k<n; k++){
                    if(mask[k][j] == 1 && visited[k][j] == 0){
                        temp += field[k][j];
                        visited[k][j] = 1;
                    }
                    else break;
                }
                
            }
            if(temp.size()) sum += stoi(temp);
        }
    }
    
    return sum;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin>>n>>m;
    int ans=-987654321;
    int cnt = 0;
    vector<string> inptString(n);
    for(int i=0; i<n; i++){
        cin>>inptString[i];
    }
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            field[i][j] = inptString[i][j];
        }
    }
    
    for(int i=0; i < (1<<(n*m)); i++){
        int mask[5][5]={0, };
        for(int j=0; j<(n*m); j++){
            if(i&(1<<j)){
//                cout<<"found: "<<j<<endl;
                int row = j/m;
                int col = j - (row*m);
//                cout<<j<<" is AT {"<<row<<", "<<col<<")"<<endl;
                mask[row][col] = 1;
            }
            cnt++;
        }
        
//        for(int i=0; i<n; i++){
//            for(int j=0; j<m; j++) cout<<mask[i][j]<<" ";
//            cout<<endl;
//        }
        
        int temp = local_result(mask);
//        cout<<"Local Ans : "<<temp<<"\n==============\n";
        ans = max(ans, temp);
    }
//    cout<<cnt<<'\n';
    cout<<ans;
    return 0;
}

가로, 세로 잇는 부분을 잘못 작성하여 한번 틀렸었습니다.