[BOJ] 14391. 종이 조각 - Java

📝 문제

문제 | 백준 14391. 종이 조각

💡 풀이 과정

⛓ 사용한 알고리즘 : 부루트 포스(brute force), 비트마스킹

아이디어 - 2가지 풀이 방식

전체 종이의 최대 크기가 4x4 이고, 종이에 적힌 숫자들의 정렬이 보장되지 않았기 때문에 모든 가능한 경우를 살펴보는 부르트포스(Brute Force)방식으로 문제를 풀이했다.

종이 한 칸이 가질 수 있는 방향성은 가로와 세로 두 가지이고, 포함될 수 있는 조각은 1x1 부터 1xN 또는 1xM 까지가 있다. 따라서 각 경우를 모두 체크해줘야 한다.

1. 재귀 함수 이용하기

재귀 함수를 사용하여 현재 위치가 1x1 부터 1xN 또는 1xM 조각에 속하는 모든 경우의 합을 구해주면 된다. 이 때 현재 위치가 가로 모양에 속해 있는지 세로 모양에 속해 있는지를 체크해줘야 하고, 모든 위치 조각을 나눴다면 자리수에 맞게 합계를 계산하면 된다.

2. 비트마스킹 이용하기

재귀 함수 방문 체크를 생각하다가 떠오른 아이디어이다. 두 방향 방문체크를 하기 위해 visit 배열을 int 형 2차원 배열로 설정한 후 가로는 1, 세로는 0으로 체크하려고 했는데, 이 2차원 배열을 가로로 쭉 나열하면 비트 형식을 띄고 있는 것이다.

예를 들어 다음과 같이 방문 체크를 한다면
1 1 1 0
1 1 0 0
0 0 1 1
0 0 1 1

다음과 같이 비트로 나타낼 수 있다. 
1110 1100 0011 0011

즉, N 과 M 이 모두 4라고 했을 경우엔 0000 0000 0000 0000 부터 1111 1111 1111 1111 까지의 경우를 살펴보면 모든 경우의 수를 파악할 수 있는 것이다.

두 방법 중 재귀함수 호출보다 비트마스킹을 이용한 방식이 더 직관적이고, 수행 시간도 빠를 것이라고 생각하여 비트마스킹을 이용해 문제를 풀이했다.

자릿수 계산

0 부터 1<<(N*M) 까지 모든 경우의 수에 대해 자릿수를 계산하여 합계를 구하면 되는데, 나는 뒤에서부터 자릿수를 증가하는 방식을 사용했다. 예를 들어 가로 숫자를 계산하는 경우, 자른 조각이 345 라면 5*1 , 4*10 , 3*100 의 순서로 계산하는 것이다. 세로의 경우도 동일하게 계산해주면 된다.

			for(int i=0;i<N;i++) { //가로 
				order=1;
				for(int j=M-1;j>=0;j--) {
					int num=j+i*M;
					if((tmp&(1<<num))>0) {
						sum += (map[i][j]*order); //자릿수 계산해서 더하기
						order*=10;
					} else { 
						order=1; //세로면 자릿수 초기화
					}
				}
			}

			for(int j=0;j<M;j++) { //세로
				order=1;
				for(int i=N-1;i>=0;i--) {
					int num = j+i*M;
					if((tmp&(1<<num))==0) {
						sum += (map[i][j]*order);
						order*=10;
					} else {
						order=1;
					}
				}
			}

다만 이 방식을 사용할 경우 가로와 세로의 인덱스를 뒤에서부터 계산하기 때문에 각각 따로 계산해줘야 한다(N 과 M 의 범위가 모두 굉장히 작기 때문에 가능한 풀이인 것 같다).

코드

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

public class Main {
	
	static int N,M;
	static int[][] map;
	
	public static void main(String[] args) 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());
		
		map = new int[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';
			}
		} //end input
		
		int max=0;
		for(int tmp=0,size=(1<<(N*M));tmp<size;tmp++) { // 모든 경우 체크
			
			int sum=0; 
			int order;
			for(int i=0;i<N;i++) { //가로 
				order=1;
				for(int j=M-1;j>=0;j--) {
					int num=j+i*M;
					if((tmp&(1<<num))>0) {
						sum += (map[i][j]*order); //자릿수 계산해서 더하기
						order*=10;
					} else { 
						order=1; //세로면 자릿수 초기화
					}
				}
			}
			for(int j=0;j<M;j++) { //세로
				order=1;
				for(int i=N-1;i>=0;i--) {
					int num = j+i*M;
					if((tmp&(1<<num))==0) {
						sum += (map[i][j]*order);
						order*=10;
					} else {
						order=1;
					}
				}
			}
			
			max = Math.max(max, sum);
		}
		
		System.out.println(max);
	}
}