[promgrammers] 자물쇠와 열쇠

문제 링크입니다

🚀 [자물쇠와 열쇠] Lv. 3 문제

이 문제를 해결하기 위해 우선 key를 뒤집어 반환하는 함수를 clockwise() 를 구현하였습니다.\

모든 경우의 수를 계산하기 위해 board를 2개의 key사이즈와 1개의 lock 사이즈의 합에 겹치는 부분 -2 를 하여 사이즈를 정해준다. (아래 그림 처럼)

board에 lock 모양을 저장하고 board에 key를 넣어보는 put함수를 구현합니다.
이후 앞서 선언한 clockwise와 를 네번 반복하는 for문과 모든 x,y를 비교하는 이중 for문으로 무작위 대입하여 문제를 해결합니다.

💎 전체 코드는 다음과 같습니다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int key_size,lock_size,board_size;

vector<vector<int> > clockwise(const vector<vector<int> >& key){
    vector<vector<int > > turned(key.size(), vector<int>(key.size(),0));
    int size = key.size();
    for(int i=0; i<key.size(); i++){
        for(int j=0; j<key.size(); j++){
            turned[i][j] = key[size-1-j][i];
        }
    }
    return turned;
}
bool put(int y, int x, vector<vector<int>> key, vector<vector<int>> board){
    // board 에 key 를 모두 더해줌
    for(int i=y; i < y+key_size; i++){
        for(int j= x; j< x+ key_size; j++){
            board[i][j] += key[i-y][j-x];
        }
    }
    // board 에 1 이 아닐경우 바로 return false;
    for(int i=key_size-1; i<board_size-key_size+1; i++){
        for(int j=key_size-1; j<board_size-key_size+1; j++){
            if(board[i][j]!=1){
                return false;
            }
        }
    }
    return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    // board = 2M -2 + N;
    key_size = key.size();
    lock_size = lock.size();
    board_size = lock.size() + (key.size()-1)*2;

    vector<vector<int> > board(board_size, vector<int>(board_size,0));
    for(int i=key_size-1; i<board_size-key_size+1; i++){
        for(int j=key_size-1; j<board_size-key_size+1; j++){
            board[i][j] = lock[i-key_size+1][j-key_size+1];
        }
    }

    for(int i=0; i<4; i++){
        for(int y=0; y <= board_size-key_size; y++){
            for(int x= 0; x<=board_size-key_size; x++){
                if(put(y,x,key,board)){
                    return true;   
                }
            }
        }
        if(i!=3) key = clockwise(key);
    }
    return false;
}