[백준] 14391번 종이 조각

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/q10000/Q14391.java

N x M 크기의 크기에 각 칸마다 숫자가 적혀있다. 이 때 가로 또는 세로로 각 칸을 아래와 같이 나눌 수 있다.

위와 같이 나눴을 경우는 493+23+58+91+9+45+7160 이 계산 된다.
2차 배열이 주어졌을 때, 가로 또는 세로로 구별을 지었을 때 최대값을 구하여라.

처음 생각

세로 N과 가로 M의 크기가 최대 4밖에 되지 않으므로 완전 탐색을 통해 답을 구할 수 있다.

다음 생각

그렇다면 어떻게 답을 도출 할 수 있을 까를 생각하는게 문제가 된다. 상태는 두가지가 주어진다. 가로 세로이다. DFS를 이용해서 1과 0으로 맵을 체크하면서 1이면 가로 0이면 세로 아니면 그 반대로 상태를 체크하면된다. 그림을 통해 알아보면 아래와 같다.

▶ 1이면 가로 0이면 세로로 가정을 하고 [3][3] 배열을 보면 다음과 같다.

▶ 모두 0이면 세로로 블럭이 만들어 진다.

▶ 모두 1이면 가로로 블럭이 만들어 진다.

▶ 가로 세로가 섞여있는 상태는 다음과 같이 볼 수 있다.

▶ 1과 0으로 표현하니 잘 와닿지 않을 수도있다. 각 칸에 숫자를 넣어보면 만들어지는 숫자는 다음과 같다.

▶ 주황색이 가로 판단이므로 543+829 이며, 파랑색이 세로 판단이므로 9+2+7이 된다. 총 값은 모두 더하면된다.

다다음 생각

따라서 위와같이 모두 0으로 시작된 상태부터 모두 1로 끝나는 상태까지 모든 조합을 만들어 주어야한다. 2차 배열에서 조합은 비트 마스크로 만들 수 도있지만 이해하기는 재귀가 더 좋으므로 재귀로 구현을 해보았다.

방안

1) 조합으로 여러 상태(가로 세로)를 생각해 볼 수 있는 문제였다.

package baekjoon.q10000;
 
import java.util.Scanner;
 
public class Q14391 {
    static int n,m;
    static int[][] arr;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // 세로 크기
        m = sc.nextInt(); // 가로 크기
        arr = new int[n][m];
        visited = new int[n][m];
        for(int i=0;i<n;i++) {
            String t = sc.next();
            for(int j=0;j<m;j++)
                arr[i][j] = t.charAt(j)-'0';
        }
        // 모든 경우의 수를 보자
        solve(0,0);
        System.out.println(result);
    }
    
    // 1 가로 0 세로
    private static void check() {
        // 가로
        int sum=0;
        for(int i=0;i<n;i++) {
            int tSum=0;
            for(int j=0;j<m;j++) {
                if(visited[i][j]==1) {
                    tSum*=10; // 연속될 시 자리수 올리기
                    tSum+=arr[i][j];
                }else {
                    sum+=tSum;
                    tSum=0; // 연속이 깨질시 초기화
                }
            }
            sum+=tSum; // 한 행 계산 결과 저장
        }
        
        // 세로
        for(int i=0;i<m;i++) {
            int tSum=0;
            for(int j=0;j<n;j++) {
                if(visited[j][i]==0) {
                    tSum*=10; // 연속될 시 자리수 올리기
                    tSum+=arr[j][i];
                }else {
                    sum+=tSum;
                    tSum=0; // 연속이 깨질시 초기화
                }
            }
            sum+=tSum;
        }
        result = Math.max(result, sum);
    }
    
    static int result;
    static int[][] visited;
    private static void solve(int x,int y) {
        // 모든 선택 완료
        if(x>=n) {
            // 검사
            check();
            return;
        }
        // 한 행 선택 완료시 다음 행으로
        if(y>=m) {
            solve(x+1,0);
            return;
        }
        // 해당 좌표 선택
        visited[x][y]=1;
        solve(x, y+1);
        visited[x][y]=0;
        
        // 해당 좌표미선택
        solve(x,y+1);
    }
}