종이 조각

📍 문제 설명

 

💡 접근

스도쿠 문제와 접근 방식은 비슷하다.

1.현재 위치의 값을 가로 숫자로 사용할 것인지 세로 숫자로 사용할 것인지 visited 배열로 판단한다.

2.모든 열을 탐색했으면 다음 행의 0열부터 다시 탐색한다.

3.모든 행을 탐색했으면 visited 배열에 맞게 가로의 합 + 세로의 합을 구한다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, answer;
    static int[][] board;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        n = kb.nextInt();
        m = kb.nextInt();
        kb.nextLine();
        board = new int[n][m];
        visited = new boolean[n][m];
        for(int i = 0; i < n; i++) {
            String[] s = kb.nextLine().split("");
            for(int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(s[j]);
            }
        }

        T.solution(0, 0);
        System.out.println(answer);

    }

    private void solution(int row, int col) {
        //마지막행까지 봤으면 이때 가로의 합 + 세로의 합을 구하기
        if(row == n) {
            sum();
            return;
        }

        //row 행의 모든열 체크 완료 -> 다음 행 확인
        if(col == m) {
            solution(row+1, 0);
            return;
        }

        //현재 위치의 값을 가로 숫자로 사용
        visited[row][col] = true;
        solution(row, col+1);

        //현재 위치의 값을 세로 숫자로 사용
        visited[row][col] = false;
        solution(row, col+1);
    }

    private void sum() {
        int total = 0; //가로+세로 합
        int sum = 0; //가로

        //가로 숫자 더하기
        for(int i = 0; i < n; i++) {
            sum = 0;
            for(int j = 0; j < m; j++) {
                if(visited[i][j]) {
                    sum *= 10; //연속되는 경우는 자릿수 변경하여 더해야함
                    sum += board[i][j];
                } else {
                    total += sum;
                    sum = 0;
                }
            }
            total += sum;
        }

        //세로 숫자 더하기
        for(int i = 0; i < m; i++) {
            sum = 0;
            for(int j = 0; j < n; j++) {
                if(!visited[j][i]) {
                    sum *= 10;
                    sum += board[j][i];
                } else {
                    total += sum;
                    sum = 0;
                }
            }
            total += sum;
        }
        answer = Math.max(answer, total);
    }
}