문제 이해

퍼즐 2개가 주어진다.
두 개 퍼즐 중 비어 있는 부분에 다른 퍼즐을 겹쳐서 1개로 만들 수 있다.
(퍼즐에 존재하는 영역 2개가 겹치는 것은 안된다)

이렇게 퍼즐 2개를 겹쳤을 때의 2개의 퍼즐을 담을 수 있는 직사각형의 최소 넓이를 구하는 문제이다.

---

문제 풀이

Brute-Force 밖에 방법이 없는 문제였다.

A와 B 퍼즐이 있을 경우 A 퍼즐은 고정시켜 놓은 상태에서 B 퍼즐을 A 퍼즐과 겹칠 수 있는지 확인하고, 만약 겹칠 수 있다면 이 때 직사각형의 넓이를 구하면 되는 문제였다.

문제는 B 퍼즐을 90, 180, 270도로 돌릴 수도 있다는 것이다. 따라서 회전시켰을 때 합치는 방법도 모두 Brute-Force로 고려해봐야한다는 추가적인 로직이 필요한 문제이다.

그렇다면 N * M 행렬을 90도 회전시키는 방법은 무엇일까?

arr[x][y]를 90도 회전시킨 행렬은 M * N 꼴의 행렬이 될 것이다.
즉, x와 y의 위치가 바뀌어야 한다는 것은 직관적으로 알 수 있다.

즉 arr[f(y)][g(x)] 값이 되는 것이다.
(0,0)을 생각해보자. 이 값은 90도 회전하면 (0, N-1)로 바뀌게 된다.
(1,0)을 생각해보자. 이 값은 90도 회전하면 (0, N-2)로 바뀌게 된다.

이처럼 다른 부분도 생각해보면 arr[x][y]는 arr[y][N-1-x]로 변환되었을 때 90도 회전을 나타냄을 알 수 있다.

나는 90, 180, 270도 회전한 arr도 모두 개별 공간에 저장해두어 Brute-Force를 적용하였다.

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		
		FastReader sc = new FastReader();

		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[][] A = new int[N][M];
		
		for(int i =0;i<N;i++) {
			String tmp = sc.next();
			for(int j=0;j<M;j++) {
				A[i][j] = tmp.charAt(j)-'0';
			}
		}
			
		int N2 = sc.nextInt();
		int M2 = sc.nextInt();
		
		int[][] B = new int[N2][M2]; // B 퍼즐
		int[][] B_90 = new int[M2][N2]; // 90도 회전 퍼즐
		int[][] B_180 = new int[N2][M2]; // 180도 회전 퍼즐
		int[][] B_270 = new int[M2][N2]; // 270도 회전 퍼즐
		
		for(int i =0;i<N2;i++) {
			String tmp = sc.next();
			for(int j=0;j<M2;j++) {
				B[i][j] = tmp.charAt(j)-'0';
			}
		}
		
		for(int i =0;i<M2;i++) {
			for(int j =0;j<N2;j++) {
				B_90[i][j] = B[N2-1-j][i];
			}
		}
		
		for(int i =0;i<N2;i++) {
			for(int j =0;j<M2;j++) {
				B_180[i][j] = B_90[M2-1-j][i];
			}
		}
		
		for(int i =0;i<M2;i++) {
			for(int j =0;j<N2;j++) {
				B_270[i][j] = B_180[N2-1-j][i];
			}
		}
		
		int x_tmp = Math.min(N, N2);
		int y_tmp = Math.min(M, M2);

		int x_right = Math.max(N, N2);
		int y_right = Math.max(M, M2);
		
		int ans = Integer.MAX_VALUE;
		
        // 0도와 180도 회전 시킨 퍼즐의 가로, 세로 크기가 동일하므로 동시에 비교
		for(int x =-x_tmp+1;x<x_right;x++) {
			for(int y =-y_tmp+1;y<y_right;y++) {
				boolean cut = false;
                
				for(int i =0;i<N2;i++) {
					for(int j =0;j<M2;j++) {
						
						if(x+i>=N || y+j>=M || x+i<0 || y+j<0) continue;
						
						if(A[x+i][y+j] == 1 && B[i][j]==1) {
							cut = true;
							break;
						}
					}
					if(cut) break;
				}
				if(!cut) {
					// cut = false일 경우에는 겹치는 퍼즐 부분이 없다는 의미
                    // 따라서 이 상황에서 직사각형의 넓이를 구해준다
                    // 아래 다른 로직들도 모두 동일
					int bottom = Math.max(N, N2+x);
					int top = Math.min(x, 0);
					
					int right = Math.max(M, M2+y);
					int left = Math.min(y, 0);
					
					
					ans = Math.min(ans, (bottom-top)*(right-left));
				}
				
				cut = false;
				for(int i =0;i<N2;i++) {
					for(int j =0;j<M2;j++) {
						if(x+i>=N || y+j>=M || x+i<0 || y+j<0) continue;
						
						if(A[x+i][y+j] == 1 && B_180[i][j]==1) {
							cut = true;
							break;
						}
					}
					if(cut) break;
				}
				if(!cut) {
					int bottom = Math.max(N, N2+x);
					int top = Math.min(x, 0);
					
					int right = Math.max(M, M2+y);
					int left = Math.min(y, 0);

					ans = Math.min(ans, (bottom-top)*(right-left));
				}
			}
		}
		
        // 90도 270도 회전시킨 퍼즐의 가로, 세로 크기가 동일하므로 동시에 비교
		for(int x =-y_tmp+1;x<y_right;x++) {
			for(int y =-x_tmp+1;y<x_right;y++) {
				
				boolean cut = false;
				for(int i =0;i<M2;i++) {
					for(int j =0;j<N2;j++) {
						if(x+i>=N || y+j>=M || x+i<0 || y+j<0) continue;
						
						if(A[x+i][y+j] == 1 && B_90[i][j]==1) {
							cut = true;
							break;
						}
					}
					if(cut) break;
				}
				if(!cut) {
					int bottom = Math.max(N, M2+x);
					int top = Math.min(x, 0);
					
					int right = Math.max(M, N2+y);
					int left = Math.min(y, 0);

					ans = Math.min(ans, (bottom-top)*(right-left));
				}
				
				cut = false;
				for(int i =0;i<M2;i++) {
					for(int j =0;j<N2;j++) {
						if(x+i>=N || y+j>=M || x+i<0 || y+j<0) continue;
						
						if(A[x+i][y+j] == 1 && B_270[i][j]==1) {
							cut = true;
							break;
						}
					}
					if(cut) break;
				}
				if(!cut) {
					int bottom = Math.max(N, M2+x);
					int top = Math.min(x, 0);
					
					int right = Math.max(M, N2+y);
					int left = Math.min(y, 0);

					ans = Math.min(ans, (bottom-top)*(right-left));
				}
			}
		}		
		
		System.out.println(ans);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과