[프로그래머스] 자물쇠와열쇠

문제설명

• 홈과 돌기로 구성된 2차원 형태의 키(N*N)와 자물쇠(M*M)가 있습니다.
• 자물쇠를 열려면 자물쇠의 홈을 다 채워야합니다.
• 키는 회전과 이동이 가능합니다.
• 키와 자물쇠가 맞닿는 영역에선 홈과 돌기가 맞아떨어져야합니다.
• 단, 자물쇠 영역 밖에 있는 키의 일부 영역에서 홈과 돌기가 있는 것은 영향을 주지 않습니다.

주어진 키와 자물쇠로 자물쇠를 열 수 있는지를 RETURN 해주세요!

아이디어

일단 N<=M<=20이란 데서 완전 탐색을 하면서 체크해봐도 되겠구나란 생각을 했다.
그래서 앵커(yolo2논문에선 박스추천을 할 중심이지만 여기선 키의 왼쪽 위 좌표)를 한 칸씩 움직여가며 4개방향을 회전해가며 열 수 있는지를 확인해주었다.

삽질했던 점

처음에 구현할 땐 4개 회전을 검사하는 2차원 반복문을 따로 구현해줬었다....ㅋㅋㅋㅋㅋ
당시 생각으론 4개 방향의 다른 버전의 키들을 각각 검사를 할 때 1개 버전의 반복문을 재활용하려면 4개 버전의 키들을 복사? 생성해야한다고 생각했었다. 매번 검사할 때마다 복사 생성하는 게 비효율적이라 생각해서 ㅋㅋㅋㅋ 4개버전의 반복문을 만들어갖고 좌표를 1:1 매핑시켰던 것이다...ㅎ.... 정말..... 멍청하면 몸이 고생한다는 것의 좋은 예시이다^^^^^..

코드를 갈아엎으면서 4개 버전의 키들을 배열에 저장해서 검사 때마다 재생성되는 걸 막아주면서 편-안해졌다..

!!!틀렸던 점!!!

아이디어에서의 앵커(키의 (0,0)이 위치할 좌표)를 (0,0)부터 (N-1,N-1)까지만 움직였었다.
근데 이렇게 하면 왼쪽과 위쪽 자물쇠 가장자리에 키가 걸친 경우를 다 탐색할 수 없다. 회전을 한다 해도 걸친 경우는 볼 수 없다(회전을 시킬 때 중심을 기준으로 했기 때문이다.)아래쪽과 오른쪽 자물쇠 가장자리 부분은 키가 걸치는 걸 검사하고 회전까지 다 검사하지만...

극단적으로 왼쪽 위 한 칸만 겹치는데 이 한 칸만 맞물리면 되는 경우를 그림으로 그려보았다.(빨강이 키 ,파랑이 자물쇠, 색깔이 돌출 하양이 홈)

이걸 질문함에 다른 분이 로직 설명하신 걸 보고서야 알았다

코드

#include <string>
#include <vector>
#include<iostream>
using namespace std;
void print_keys(int k[20][20],int ksz){
    for(int i = 0;i<ksz;i++){
        for(int j =0;j<ksz;j++){
            cout<<k[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
bool x_o_r(int a, int b){
    return (a==1&&b==0)||(a==0&&b==1);
}
int fits(int k[20][20],int ksz,int ii, int jj, vector<vector<int>> &lock){
    int valid = true;
    int fill = 0;
    int li, lj;
    //cout<<"ksz"<<ksz<<endl;
    for(int i = 0;i<ksz;i++){
        li = ii+i;
        
        for(int j= 0;j<ksz;j++){
            lj=jj+j;
            if(!(li>=0&&li<lock.size()&&lj>=0&&lj<lock.size())){
                //cout<<"outofbound : "<<li<<" "<<lj<<endl;
                continue;
            }
            else{
                //cout<<"safe : "<<li<<" "<<lj<<endl;
            }
            if(x_o_r(k[i][j],lock[li][lj])){
                if(k[i][j] == 1&&lock[li][lj]==0){
                    fill++;
                }
            }
            else{
                valid = false;
                break;
            }
        }
    }
    
    return (valid?fill:-1);
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    //key[0]
    
    int rot_key[4][20][20];
    int ksz = key.size();
    for(int i = 0;i<ksz;i++){
        for(int j = 0;j<ksz;j++){
            rot_key[0][i][j] =key[i][j];
            rot_key[1][j][ksz-1-i] = key[i][j];
            rot_key[2][ksz-1-i][ksz-1-j] = key[i][j];
            rot_key[3][ksz-1-j][i] = key[i][j];
        }
    }
    
    for(int i = 0;i<4;i++){
        cout<<"i : "<<i<<" print\n";
        print_keys(rot_key[i],ksz);
    }
    int mother_u = 0;
    for(int i = 0;i<lock.size();i++){
        for(int j =0;j<lock.size();j++){
            if(lock[i][j] == 0) mother_u++;
        }
    }
    
    cout<<"checking"<<endl;
    bool valid = false;
    int lsz = lock.size();
    for(int i = 0-key.size()+1;i<lsz;i++){
        for(int j = 0-key.size()+1;j<lsz;j++){//시작점
            for(int k= 0;k<4;k++){//키버전
                //cout<<"kkkkk"<<k<<endl;
                if(mother_u ==fits(rot_key[k],ksz, i,j,lock)){
                    valid = true;
                    cout<<i<<" "<<j << " " << k << " " << mother_u<<endl;
                    break;
                }
            }
            if(valid) break;
        }
        if(valid) break;
    }
    answer= valid;
    return answer;
}