백준 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;
}