백준 21277번 - 짠돌이 호석

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

21277번: 짠돌이 호석

 

• 문제 해결 방법

어려운 알고리즘을 필요로 하진 않지만 구현이 힘든 문제였습니다.

퍼즐의 최대 크기가 50x50으로 작기 때문에 완전탐색으로도 충분히 풀어낼 수 있습니다.

 

 

두개의 퍼즐 배치 예시

 

완전탐색을 위해서 회전된 퍼즐마다 위와 같은 상황들을 모두 비교해야 하는데 그러기 위해선 최대 150*150 크기의 배열이 필요합니다. 여기서 수행시간을 줄이기 위해서는 N,M의 크기마다 정확한 인덱싱으로 두 퍼즐이 겹치는지 아닌지 비교해야 겠지만, 저는 첫번째 퍼즐을 (50,50)의 위치에 고정시켜 두고 두번째 퍼즐과 합쳐질 수 있는지 모든 경우를 비교했습니다. 합쳐질 수 있는 경우 그때의 액자의 크기를 구하고 최솟값을 저장하면 문제를 해결할 수 있습니다.

 

 

 

• C++ 전체 코드

#include<bits/stdc++.h>
using namespace std;

int N,M;
int tN,tM;
int m[150][150]{}; // 퍼즐1
int sub[50][50]{}; // 퍼즐2

bool chkOverlap(int y, int x){ // 겹치면 true반환
    for(int i=0; i<tN; i++){
        for(int j=0; j<tM; j++){
            if(sub[i][j] && m[i+y][j+x])
                return true;
        }
    }
    return false;
}

int comp(){
    int minArea = 1e9;
    for(int i=0; i<150-tN; i++){
        for(int j=0; j<150-tM; j++){
            if(chkOverlap(i,j)) continue; // 겹치면 continue
            // 합쳐질 수 있는경우 그때의 액자크기 계산
            int miny = min({i, i+tN, 50, 50+N});
            int minx = min({j, j+tM, 50, 50+M});
            int maxy = max({i, i+tN, 50, 50+N});
            int maxx = max({j, j+tM, 50, 50+M});
            int sum = (maxy-miny) * (maxx-minx);
            minArea = min(minArea, sum);
        }
    }
    return minArea;
}

void rotate(){ // 액자2를 시계방향으로 90도 회전
    int t[tM][tN]{};
    for(int j=0, ii=0; j<tM; j++, ii++){
        for(int i=tN-1, jj=0; i>=0; i--, jj++){
            t[ii][jj] = sub[i][j];
        }
    }
    swap(tN, tM); // 회전시 N,M 크기도 바꿔주어야 함
    for(int i=0; i<tN; i++){
        for(int j=0; j<tM; j++){
            sub[i][j] = t[i][j];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string str;
    cin>>N>>M;
    for(int i=50; i<50+N; i++){ // 퍼즐1의 시작위치를 50,50에 고정
        cin>>str;
        for(int j=50; j<50+M; j++){
            m[i][j] = str[j-50] - '0';
        }
    }

    cin>>tN>>tM;
    for(int i=0; i<tN; i++){
        cin>>str;
        for(int j=0; j<tM; j++){
            sub[i][j] = str[j] - '0';
        }
    }
    
    int ans = 1e9;
    ans = min(ans, comp());
    rotate();
    ans = min(ans, comp());
    rotate();
    ans = min(ans, comp());
    rotate();
    ans = min(ans, comp());
    cout<<ans;
}