풀이

아이디어

이 문제를 어떤식으로 풀어야 될지 감도 안잡히는 상태에서 이 문제가 브루트포스에 비트마스킹으로 풀어야 된다는 것을 보고 도저히 생각이 나지 않아 다음 블로그 포스트를 참고하였습니다.

https://code-lab1.tistory.com/101

블로그에서 자세히 설명이 되어 있는데 단순히 이 mat[i][j]가 0이면 세로고 1이면 가로야! 라고 표시를 한겁니다.

문제의 예제를 가져와서 설명해드리겠습니다.

다음과 같이 표현된 사각형을 이제 1110 0010 0000 1100 으로 표현을 할 수 있는 겁니다. 즉 N * M의 비트수만큼의 비트마스킹을 통해 현재 직사각형의 상태를 볼 수 있고 이를 계산하면 되는 것입니다.

1. 0부터 1 << (N * M) 만큼의 범위의 직사각형 표현 방식을 브루트포스하게 검사합니다.
2. 검사하여 나온 최댓값을 저장하고 출력합니다. 이러한 저장된 값들을 비트마스킹으로 문제를 풀면 됩니다.

상세 구현

1. 0부터 1 << (N * M) 만큼의 범위의 직사각형 표현 방식을 브루트포스하게 검사합니다.

		for(int i=0; i< (1<<(N*M)); i++) {
			check(i);
		}

다음을 통해 0부터 1111~1111까지의 모든 경우를 탐색하게 됩니다.

2. 검사하여 나온 최댓값을 저장하고 출력합니다.
   이제 각 값들을 구해야 합니다. 이를 구하기 위해 2중 포문으로 검색하여 가로 직사각형/ 세로 직사각형을 구해줘야 합니다.

	private static void check(int num) {
		int sum = 0;
		// 가로 찾기
		for(int i=0; i<N; i++) {
			int cur = 0;
			for(int j=0; j<M; j++) {
				int k = i * M + j;
				if((num & (1<<k)) == 0) {
					cur *= 10;
					cur += mat[i][j];
				}else {
					sum += cur;
					cur = 0;
				}
			}
			sum += cur;
		}
		// 세로 찾기
		for(int j=0; j<M; j++) {
			int cur = 0;
			for(int i=0; i<N; i++) {
				int k = i*M + j;
				if((num & (1<<k)) != 0) {
					cur *= 10;
					cur += mat[i][j];
				}else {
					sum += cur;
					cur = 0;
				}
			}
			sum += cur;
		}
		max = Math.max(max, sum);
	}

이를 통해 총 가로 직사각형들과 세로 직사각형들의 합을 구할 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class No14391 {
	static int N, M, max;
	static int[][] mat;
	public static void main(String[] args) throws IOException {
		input();
		pro();
	}
	private static void input() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		mat = new int[N][M];
		
		for(int i=0; i<N; i++) {
			String line = br.readLine();
			for(int j=0; j<M; j++) {
				mat[i][j] = line.charAt(j)-'0';
			}
		}
		br.close();
	}
	private static void pro() {
		max = 0;
		for(int i=0; i< (1<<(N*M)); i++) {
			check(i);
		}
		System.out.println(max);
	}
	private static void check(int num) {
		int sum = 0;
		// 가로 찾기
		for(int i=0; i<N; i++) {
			int cur = 0;
			for(int j=0; j<M; j++) {
				int k = i * M + j;
				if((num & (1<<k)) == 0) {
					cur *= 10;
					cur += mat[i][j];
				}else {
					sum += cur;
					cur = 0;
				}
			}
			sum += cur;
		}
		// 세로 찾기
		for(int j=0; j<M; j++) {
			int cur = 0;
			for(int i=0; i<N; i++) {
				int k = i*M + j;
				if((num & (1<<k)) != 0) {
					cur *= 10;
					cur += mat[i][j];
				}else {
					sum += cur;
					cur = 0;
				}
			}
			sum += cur;
		}
		max = Math.max(max, sum);
	}
}