백준 21277번 짠돌이 호석

문제 요약

$ N_1 \times M_1 $ 퍼즐이 하나, $ N_2 \times M_2 $ 퍼즐이 하나 주어진다. 각 테이블엔 0 또는 1이 적혀져 있다.

각 퍼즐은 90도씩 회전이 가능하다. 이 때, 이 두 퍼즐을 합치려고 하는데 서로 1이 적혀져 있는 부분이 겹치지 않으면 둘이 겹치는 것도 가능하다.

이런 식으로 두 퍼즐을 합쳤을 때 이 두 퍼즐을 포함하는 최소 크기의 직사각형의 넓이 중 최소를 출력하시오

$ 1 \le N_1, M_1, N_2, M_2 \le 50$

풀이

놓을 수 있는 방법을 생각해보자. 퍼즐 하나를 고정시켜놓고 다른 퍼즐 하나를 놓는다고 하자.

고정 시킨 퍼즐이 $ N_1 \times M_1$이라고 한다면 $ N_2 \times M_2 $ 퍼즐을 놓아볼 수 있는 곳은 고정된 퍼즐의 모든 위치 (1, 1), (1, 2), ... , $(N_1, M_1)$에다가 퍼즐의 바로 바깥 $(1, M_1 + 1), (1, M_1+1), \ldots (N_1+1, M_1+1), (N_1+1, M_1), \ldots, (N_1+1, 1)$ 까지 총 $(N_1+1) \times (M_1+1)$가지의 위치 후보가 있다.

그럼 이 모든 곳에 놓아보고 두 퍼즐에 적힌 1끼리 서로 겹치는 부분이 있는지 판단 하는 데에는 고정된 퍼즐의 크기만큼 걸릴 것이다.

이를 시간복잡도로 나타내면 $O(N_1^2 M_1^2)$정도인데 퍼즐끼리 회전이 가능하다고 했다. 그래서 고정된 퍼즐의 회전 가짓수 4, 놓을 퍼즐의 회전 가짓수 4를 곱해줘야 한다.

그리고 $ N_1 \times M_1 $짜리 퍼즐만 고정시킬 게 아니라 $ N_2 \times M_2 $짜리 퍼즐도 고정시켜봐야 한다. 그래서 대략 상수가 32인데 이러면 $50^4 \times 32 = 2 \times 10^8$, 2억 정도로 시간 내에 충분히 돌아간다.

그럼 이제 $(y, x)$에 퍼즐을 놓는데 성공했을 때의 최소 직사각형의 넓이는 어떻게 구할까?

세로 높이와 가로 길이 $H, W$는 각각 $H = max(N_1, y+N_2-1), W = max(M_1, x+M_2-1)$이 되고 이를 곱해주자.

#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int n1, m1, n2, m2;
int c[105][105];
vector<vector<int>> a(55, vector<int>(55, 0));
vector<vector<int>> b(55, vector<int>(55, 0));

void rotate(vector<vector<int>> &v, int &N, int &M) {
    vector<vector<int>> tmp = v;
    for(int i=1;i<=M;++i) {
        for(int j=1;j<=N;++j) {
            tmp[i][j] = v[N-j+1][i];
        }
    }
    v = tmp;
    swap(N, M);
}

// put b's left-upper side at (y, x) of a
bool solve(int y, int x) {
    for(int i=y;i<=n1;++i) {
        for(int j=x;j<=m1;++j) {
            if(a[i][j] == 0) continue;
            int k = i-y+1;
            int l = j-x+1;
            if(1<=k && k<=n2 && 1<=l && l<=m2 && b[k][l] == 1)
                return false;
        }
    }
    return true;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> n1 >> m1;
    for(int i=1;i<=n1;++i) {
        string s; cin >> s;
        for(int j=1;j<=m1;++j) {
            a[i][j] = s[j-1] - '0';
        }
    }
    cin >> n2 >> m2;
    for(int i=1;i<=n2;++i) {
        string s; cin >> s;
        for(int j=1;j<=m2;++j) {
            b[i][j] = s[j-1] - '0';
        }
    }
    int ans = INF;
    for(int i=0;i<4;++i) {
        memset(c, 0, sizeof(c));
        for(int i=1;i<=n1;++i) for(int j=1;j<=m1;++j) c[i][j] = a[i][j];
        for(int j=0;j<4;++j) {
            for(int k=1;k<=n1+1;++k) {
                for(int l=1;l<=m1+1;++l) {
                    if(solve(k, l)) {
                        int H = max(n1, k+n2-1);
                        int W = max(m1, l+m2-1);
                        ans = min(ans, H*W);
                    }
                }
            }
            rotate(b, n2, m2);
        }
        rotate(a, n1, m1);
    }
    swap(a, b);
    swap(n1, n2);
    swap(m1, m2);
    for(int i=0;i<4;++i) {
        memset(c, 0, sizeof(c));
        for(int i=1;i<=n1;++i) for(int j=1;j<=m1;++j) c[i][j] = a[i][j];
        for(int j=0;j<4;++j) {
            for(int k=1;k<=n1+1;++k) {
                for(int l=1;l<=m1+1;++l) {
                    if(solve(k, l)) {
                        int H = max(n1, k+n2-1);
                        int W = max(m1, l+m2-1);
                        ans = min(ans, H*W);
                    }
                }
            }
            rotate(b, n2, m2);
        }
        rotate(a, n1, m1);
    }
    cout << ans << '\n';
    return 0;
}