[백준] 14391번 종이조각

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

14391번: 종이 조각

 

import java.util.*;
import java.io.*;

public class Main {

    public static int N;
    public static int M;
    public static int[][] map;
    public static boolean[][] visit;
    public static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        visit = new boolean[N][M];
        for(int i = 0; i < N; i++) {
            String s = br.readLine();
            for(int j = 0; j < M; j++) {
            	map[i][j] = s.charAt(j) - '0';
            }
        }

        dfs(0, 0);
        System.out.println(max);
    }

    public static void dfs(int row, int col) {
        // 전체 행 탐색종료
        if(row >= N) {
        	sum();
        	return;
        }

        // 한줄 탐색 완료, 다음 행으로 이동
        if(col >= M) {
        	dfs(row + 1, 0);
        	return;
        }    

        // 가로
        visit[row][col] = true;
        dfs(row, col + 1);

        // 세로
        visit[row][col] = false;
        dfs(row, col + 1);
    }


    public static void sum() {
        int ret = 0;
        int temp = 0;


        // 가로 숫자 계산
        for(int i = 0; i < N; i++) {
        	temp = 0;
            for(int j = 0; j < M; j++) {
                // 가로 덧셈 : true (가로로 자른 값 연속)
                if(visit[i][j]) {
                    temp *= 10; // 자릿수 이동 : 1 -> 10
                    temp += map[i][j]; // 10 -> 13
           		 } else { // 세로로 자른 값 만났을 때
                    ret += temp;
                    temp = 0;
                }
            }
            ret += temp;
        }

        // 세로 숫자 계산
        for(int i = 0; i < M; i++) {
            temp = 0;
            for(int j =0; j < N; j++) {
                // 세로 덧셈 : false (세로로 자른 값 연속)
                if(!visit[j][i]) {
                    temp *= 10;
                    temp += map[j][i];
                } else { // 가로로 자른 값 만났을 때
                    ret += temp;
                    temp = 0;
                }
            }
            ret += temp;
        }
        max = Math.max(max, ret);
    }
    
}