[ boj : 21277 ] 짠돌이 호석

https://www.acmicpc.net/problem/21277

21277번: 짠돌이 호석

문제 : 2개의 퍼즐이 주어지고 이 퍼즐을 겹쳤을때 딱 맞게 겹쳐져야 합니다. 이때 만들 수 있는 최소 넓이를 구하시오

해설 : 이건 어렵게 생각할 필요가 전혀 없습니다. 그냥 뇌를 비우고 하라는 데로 하면 됩니다. 무슨 뜻이냐면 모든 경우의 수를 다 해보면 됩니다. 문제 조건에서 N과 M이 떡하니 제한이 50이라는 것은 너 이거 무식하게 풀어!!라는 뜻이니까요.

그러면 천천히 봐보죠. 먼저 첫번째 퍼즐을 (0,0)으로 시작해버리면 시작부터 꼬여버리게 됩니다. 퍼즐의 크기는 최대 50이니깐 (50,50)부터 시작하는 것 입니다. 그 이유는 2번째 퍼즐이 1번째 퍼즐의 격자와 겹쳐버리는 것부터 시작해야 되기 때문입니다. 그림으로 보시죠

이것처럼 2번째 퍼즐이 이런식으로 1번째 퍼즐과 겹쳐버릴 수 있는 것입니다.

이것만 체크한다면 그 이후부터는 구현문제입니다. 배열을 돌리는 법은 길이(NxM) 인 직사각형은 오른쪽으로 90도 만큼 회전을 시킨다면 (MxN)인 직사각형으로 변환이 됩니다. 그럼 각 열에 해당하는 수들은 그대로 행으로 변환이 됩니다. 

이게 무슨 뜻이냐면

현재 왼쪽 배열에서 빨간색박스 안에 있는 수들은 (x,0) 의 좌표값을 가지고 있는 친구들입니다. 이 친구들을 오른쪽으로 90도 만큼 회전을 시킨다면 (x,0) 인 친구들이 (0,x) 인 좌표값을 가지게 됩니다.

따라서

for (int i = 0; i < c; i++)
		for (int j = 0; j < r; j++) {
			temp[i][r - j - 1] = puzzle[j][i];
			puzzle[j][i] = 0;
		}

이런 방법을 통해서 배열을 옮겨주면 됩니다.

180도 270도 는 그냥 이 동작을 2번 3번 해주면 되겠죠. 이렇게 모든 가능한 경우의 좌표값에서 비교하고 회전시키고 비교하고 회전시키고 를 3번 하고 4번째에는 다시 원상태로 돌아오게 되는 것이니 한칸 옮겨주면 됩니다.

#include<bits/stdc++.h>

using namespace std;

int n, m, r, c;
int board[210][210],puzzle[55][55];
const int INF = (int)1e9;
int ans = INF;

void rotate();
int solve(int x, int y);

int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 50; i < n + 50; i++)
		for (int j = 50; j < m + 50; j++)
			scanf("%1d", &board[i][j]);
	cin >> r >> c;
	for (int i = 0; i < r; i++)
		for (int j = 0; j < c; j++)
			scanf("%1d", &puzzle[i][j]);
	for(int i=0;i<=200;i++)
		for (int j = 0; j <= 200; j++) {
			if (i + r > 200 || i + c > 200 || j + c > 200 || j + r > 200)continue;
			if ((i + r < 50 && j + c < 50) || (n+50<=i && m+50<=j))continue;
			for (int k = 0; k < 4; k++) {
				ans = min(ans,solve(i, j));				
				rotate();
				swap(r, c);
			}
		}
	cout << ans;
	return 0;
}
void rotate()
{
	int temp[55][55];
	for (int i = 0; i < c; i++)
		for (int j = 0; j < r; j++) {
			temp[i][r - j - 1] = puzzle[j][i];
			puzzle[j][i] = 0;
		}
	for (int i = 0; i < c; i++)
		for (int j = 0; j < r; j++)
			puzzle[i][j] = temp[i][j];
}
int solve(int x,int y)
{
	for(int i=x,p=0;i<x+r;i++,p++)
		for (int j = y,q=0; j < y + c; j++,q++)
			if (board[i][j] != 0 && puzzle[p][q]!=0)return INF;
	
	int minx = min(x, 50), maxx = max(x + r, n + 50)-1;
	int miny = min(y, 50), maxy = max(y + c, m + 50) - 1;
	int sero = abs(minx - maxx)+1;
	int garo = abs(miny - maxy)+1;
	return sero * garo;
}