[BOJ] 14391. 종이 조각

비트마스킹을 이용한 완전탐색으로 해결한 문제이다.

이 문제를 맨처음 봤을땐 아이디어가 잘 생각안지 않았다. 곰곰히 생각해보니 어차피 빈칸 하나에 대해선 가로 방향 또는 새로 방향을 가질 수 있으므로 전체가지수를 2^(가로X세로) 로 생각하고 모든 경우에 대해 값을 계산해보는 방법을 생각해냈다. 2가지의 경우를 가지기 때문에 비트마스킹을 이용하여 모든 subSet을 가로는 -1, 세로는 1로 표현하여 dir이란 배열에 대입해주어 계산하였다. 그 후 해당 경우에서 가로, 세로를 따로 계산하여 더한값을 최종답으로 갱신해주며 풀었다.

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_14391_종이조각 {
    
    static int[][] map;
    static int[][] dir;
    
    static int answer;
    
    static int R,C;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        R=Integer.parseInt(st.nextToken());
        C=Integer.parseInt(st.nextToken());
        
        map=new int[R][C];
        dir=new int[R][C];
        for(int i=0;i<R;i++) {
            String str=br.readLine();
            for(int j=0;j<C;j++) {
                map[i][j]=Integer.parseInt(str.charAt(j)+"");
            }
        }
        answer=0;
        setDirWithBit();
        System.out.println(answer);
    }
    
    static void setDirWithBit() {
        for(int i=0;i<(1<<R*C);i++) {
            for(int j=0;j<R*C;j++) {
                if((i & (1<<j)) !=0) {    //가로
                    dir[j/C][j%C]=-1;        
                }else {                    //세로
                    dir[j/C][j%C]=1;    
                }
            }
            calcSum();
        }
        
    }
    
    static void calcSum() {
        int rowSum=0;
        for(int i=0;i<R;i++) {        //모든 가로행의 합
            int sum=0;
            for(int j=0;j<C;j++) {
                if(dir[i][j]==-1) {
                    sum=(sum*10) + map[i][j];
                }else {
                    rowSum+=sum;
                    sum=0;
                }
            }
            rowSum+=sum;
        }
        
        int colSum=0;
        for(int i=0;i<C;i++) {        //모든 새로행의 합
            int sum=0;
            for(int j=0;j<R;j++) {
                if(dir[j][i]==1) {
                    sum=(sum*10) + map[j][i];
                }else {
                    colSum+=sum;
                    sum=0;
                }
            }
            colSum+=sum;
        }
        
//        System.out.println(rowSum+colSum);
        answer=Math.max(answer, rowSum+colSum);
    }
    
    
    
}