[BOJ] 21277 짠돌이 호석

생각 정리

1. 4개의 모서리에 최소 하나의 1이 존재 -> 4개의 모서리를 확인 후 1인 경우 건너뛰려고 했다.

2. 최대 넓이가 50x50이고, 회전 하지 않았을 때, 90도, 180도, 270도 총 4가지를 비교하면 50x50(A퍼즐)x50x50(B퍼즐)x4 = 25,000,000가지로 생각(하나의 퍼즐을 고정해야겠다는 생각을 하지 못했다.)

3. 두 개 퍼즐의 행과 열이 다른 경우에 맞춰주려고 함 -> 하나를 고정해야겠다는 생각을 못해서 n1 > n2이고, m1<m2인 경우와 n1 < n2이고, m1 > m2인 경우 0을 채워서 행과 열을 같게 맞춰주려고 했다.

4. 0, 90, 180, 270도 회전을 했을 때 각각 생각 -> swap()을 생각하지 못하고 회전 경우마다 for문을 생성해서 각각을 고려해주려고 했다.

결론 : 중첩된 for문이 너무 많이 나와서 생각이 따라가지를 못해서 풀이 참고 -> 아예 방향을 잘못 접근하고 있었다.

---

소스 코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr1[51][51];
int arr2[51][51];
int ans[151][151];
int n1, m1, n2, m2, result=987654321;
void solution(int y, int x) {
	bool flag = false;
	for (int i = y; i < y + n2; i++) {
		for (int j = x; j < x + m2; j++) {
			if (ans[i][j] == 1 && arr2[i - y][j - x] == 1) {
				flag = true;
				break;
			}
		}

		if (flag) break;
	}

	if (flag == false) {
		int minx = min(x, 50); 
		int miny = min(y, 50);
		int maxx = max(x + m2 - 1, 49 + m1);
		int maxy = max(y + n2 - 1, 49 + n1);

		int space = (maxx - minx+1) * (maxy - miny+1);
		result = min(result,space);

	}
}

void rotate() {
	int temp[51][51] = { 0, };
	for (int i = m2 - 1; i >= 0; i--) {
		for (int j = 0; j < n2; j++) {
			temp[m2 - 1 - i][j] = arr2[j][i];
		}
	}

	for (int i = 0; i <= 50; i++) {
		for (int j = 0; j <= 50; j++) {
			arr2[i][j] = temp[i][j];
		}
	}
	swap(n2, m2);
}
int main(void) {
	cin >> n1 >> m1;
	for (int i = 0; i < n1; i++) {
		for (int j = 0; j < m1; j++) {
			char temp; 
			cin >> temp;
			arr1[i][j] = temp-'0';
		}
	}

	cin >> n2 >> m2;
	for (int i = 0; i < n2; i++) {
		for (int j = 0; j < m2; j++) {
			char temp;
			cin >> temp;
			arr2[i][j] = temp - '0';
		}
	}

	// 퍼즐 1번 고정
	for (int i = 0; i < n1; i++) {
		for (int j = 0; j < m1; j++) {
			ans[i + 50][j + 50] = arr1[i][j];
		}
	}

	for (int k = 0; k < 4; k++) {
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				solution(i, j);
			}
		}
		rotate();
	}

	cout << result << '\n';
}