[BOJ] 21277 짠돌이 호석

짠돌이 호석

1번째 퍼즐
N1 * M1

2번째 퍼즐
N2 * M2

액자 가격 = 행의 개수 * 열의 개수
90도 180도 270도 회전 가능
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
큰 퍼즐을 가운데에 기준으로 잡고 사방으로 돌려가면서  붙여보기

1. 큰 퍼즐 / 작은 퍼즐 구분

--> 이 방법은 어차피 어떤 퍼즐을 기준으로 잡고 놓아도 똑같은 방식이기 때문에 첫번째 퍼즐을 기준으로 잡았다

모든 방법 다 해봐야함
0 90 180 270 4가지 방안 확인해야함

비교해볼 때 시작할 위치를 정하는 방법이 2가지 존재
0,0 부터 100,100 까지 다 검색 하거나
or
크기에 맞춰서 a*b 크기면 50-a, 50-b 에서 부터 시작하는 방식이 있다.

그러나 후자의 방법으로 할 시 복잡하거나 헷갈린다는 조언을 듣고 전자 방식으로 수행

따라서 0,0부터 한 퍼즐의 최대 크기인 50*50을 통해 100, 100까지 전체 탐색

---

전체적인 구성

입력 -> (확인 -> 회전(90도)) x 4 -> 가장 작은 넓이 출력

 

처음 코드 (10/19)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int mp1[51][51], mp2[51][51];
int ans[151][151];
int n1, n2, m1, m2;
int result  = 999999;

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

    for (int i = 0; i <= 50; i++) {
		for (int j = 0; j <= 50; j++) {
			mp2[i][j] = tmp[i][j];
		}
	}
    swap(n2,m2);
}


void check(int x, int y){
    bool check = true;
    for(int i = x; i < x + n2; i++){
        for(int j = y; j < y + m2; j++){
            if(ans[i][j] == 1 && mp2[i-x][j-y] == 1){
                check = false;
            }
            break;
        }
        if(check == false){
            break;
        }
    }
    if(check == true){
        int x1 = min(x,50);
        int x2 = max(x + m2-1, 49 + m1);
        int y1 = min(y,50);
        int y2 = max(y+ n2-1, 49 + n1);

        int area = (x2-x1+1) * (y2-y1+1);
        result = min(result, area);
    }

}


int main(){
    
    //1번 퍼즐
    cin >> n1>> m1;
    for(int i = 0; i < n1; i++){
        for(int j = 0; j < m1 ; j++){
            char tmp; cin>>tmp;
            mp1[i][j] = tmp - '0';
        }
    }
    //2번 퍼즐
    cin >> n2>> m2;
    for(int i = 0; i < n2; i++){
        for(int j = 0; j < m2 ; j++){
            char tmp; cin>>tmp;
            mp2[i][j] = tmp - '0';
        }
    }

    //1번 퍼즐 고정
    for(int i = 0; i < n1; i++){
        for(int j = 0; j < m1 ; j++){
            ans[50+i][50+j] = mp1[i][j];
        }
    }   
    // 0 90 180 270 돌려가면서 ans[50][50] 부터 ans[50+n1][50+m1] 다 확인
    for(int i = 0; i<4; i++){ //회전 4번
        //ans[0][0] 부터 다 확인
        for(int j = 0; j<100; j++){
            for(int k = 0 ; k < 100; k++){
                check(j, k);
            }
        }
        rotate();
    }
    
    cout << result << "\n";

}

--> 해당 코드는 check 함수에서 break의 위치를 잘못 넣어 10개의 test case만 만족했다. 맞왜틀의 구렁텅이에서 벗어나지 못하다가 풀이를 보고나서  break위치가 틀렸음을 알게됐다.

수정 후 (19/19)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int mp1[51][51], mp2[51][51];
int ans[151][151];
int n1, n2, m1, m2;
int result  = 999999;

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

    for (int i = 0; i <= 50; i++) {
		for (int j = 0; j <= 50; j++) {
			mp2[i][j] = tmp[i][j];
		}
	}
    swap(n2,m2);
}


void check(int x, int y){
    bool check = true;
    for(int i = x; i < x + n2; i++){
        for(int j = y; j < y + m2; j++){
            if(ans[i][j] == 1 && mp2[i-x][j-y] == 1){
                check = false;
                break;
            }
        }
        if(check == false){
            break;
        }
    }
    if(check == true){
        int x1 = min(x,50);
        int x2 = max(x + n2-1, 49 + n1);
        int y1 = min(y,50);
        int y2 = max(y+ m2-1, 49 + m1);

        int area = (x2-x1+1) * (y2-y1+1);
        result = min(result, area);
    }

}


int main(){
    
    //1번 퍼즐
    cin >> n1>> m1;
    for(int i = 0; i < n1; i++){
        for(int j = 0; j < m1 ; j++){
            char tmp; cin>>tmp;
            mp1[i][j] = tmp - '0';
        }
    }
    //2번 퍼즐
    cin >> n2>> m2;
    for(int i = 0; i < n2; i++){
        for(int j = 0; j < m2 ; j++){
            char tmp; cin>>tmp;
            mp2[i][j] = tmp - '0';
        }
    }

    //1번 퍼즐 고정
    for(int i = 0; i < n1; i++){
        for(int j = 0; j < m1 ; j++){
            ans[50+i][50+j] = mp1[i][j];
        }
    }   
    // 0 90 180 270 돌려가면서 ans[50][50] 부터 ans[50+n1][50+m1] 다 확인
    for(int i = 0; i<4; i++){ //회전 4번
        //ans[0][0] 부터 다 확인
        for(int j = 0; j<100; j++){
            for(int k = 0 ; k < 100; k++){
                check(j, k);
            }
        }
        rotate();
    }
    
    cout << result << "\n";
    return 0;
}

다음부턴....break 같은 사소한 실수를 하지 않도록 노력하겠습니다.......