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

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

문제 링크

#include <string>
#include <vector>

using namespace std;
int keysize;
int locksize; 
int boardsize;
void turn(vector<vector<int>> &key)
{
    vector<vector<int>> temp(key.size(), vector<int>(keysize));
    for (int i = 0; i < key.size(); i++){
        int idx = keysize - 1;
        for (int j = 0; j < keysize; j++){
            temp[i][idx--] = key[j][i];
        }
    }
    key.assign(temp.begin(), temp.end());
}

bool check(int x, int y, vector<vector<int>>& key, vector<vector<int>>& board){
    
    //키를 더한다
    vector <vector<int>> checkBoard;
    checkBoard.assign(board.begin(), board.end());
    for(int i=x; i <x + key.size(); i++){
        for(int j=y; j < y +keysize; j++){
            checkBoard[i][j] += key[i - x][j - y];
        }
    }

    for(int i=key.size() - 1; i <= checkBoard.size() - key.size(); i++){
        for(int j=keysize - 1; j<=checkBoard.size() - keysize; j++){
            if(checkBoard[i][j] != 1) return false;
        }
    }
    
    return true;
}
bool initCheck(vector<vector<int>>& lock){
    for(int i=0; i<lock.size(); i++){
        for(int j=0; j<lock[0].size(); j++){
            if(!lock[i][j]) return false;
        }
    }
    return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
    bool answer = false;
    
    //자물쇠의 빈칸이 없는 경우
    if(initCheck(lock)) return true;
    locksize = lock.size();
    keysize = key.size();
    boardsize = lock.size() + (keysize -1) * 2;
    vector<vector<int>> board(boardsize, vector<int>(boardsize, 0));

    //lock을 더해 놓는다.
    for (int i = keysize - 1; i <= boardsize - keysize; i++)
        for (int j = keysize - 1; j <= boardsize - keysize; j++)
            board[i][j] = lock[i - keysize + 1][j - keysize + 1];



    for (int r = 0; r < 4; r++){ 
        //상하좌우 돌리기
        for(int i=0; i<=boardsize - keysize; i++){
            for(int j=0; j<=boardsize - keysize; j++){
                //lock에 하나씩 맞춰보기
                if(check(i, j, key, board)) return true;
            }
        }
        turn(key);

    }
    return answer;
}

• N과 M이 최대 20까지 밖에 없으므로 완전탐색으로 풀었다.
  1. 키를 돌린다.
  2. 모든 칸에 대본다.
  3. 맞다면 return true

• 키를 갔다 댈 때, 최소 시작점부터 최대 시작점까지 한 번씩 갔다 대면 된다.
• (0, 0)부터 시작 해서 boardsize - keysize만큼 갔다 대면 된다.