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

기본 틀은 짠돌이 호석과 비슷하게 풀었습니다. 짠돌이 호석 문제를 풀어봐서 그런지 딱 봤을 때 어떻게 접근을 해야 할지는 바로 보였던 것 같습니다. 

lock을 고정시킨 뒤에 key의 위치를 옮기고, 회전시키면서 정답이 나오는지(lock의 0 부분을 1로 다 채울 수 있는지) 체크해주었습니다. background에서 key의 배열을 더해주고 난 뒤(lock의 1과 key의 1이 겹치지 않고, key의 0과 lock의 0이 겹치지 않으면 무조건 1이 나오게 된다.), lock 부분에 0이 있거나 2가 있다면 정답이 될 수 없기 때문에 그런 경우 check 함수에서 바로 false를 return 합니다. 

다른 부분보다 vector의 구조를 이번 문제처럼 사용해본 적이 없어서 background 선언 형식을 참고하였습니다.

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

using namespace std;
int keys, locks;

bool check( vector<vector<int>> background, vector<vector<int>> key, int x, int y){
    for(int i=x;i<x+keys;i++){
        for(int j=y;j<y+keys;j++){
            background[i][j] += key[i-x][j-y]; 
        }
    }
    for(int i=keys;i<keys+locks;i++){
        for(int j=keys;j<keys+locks;j++){
            if(background[i][j]==1) continue;
            return false;
        }
    }

    return true;
}

void rotate(vector<vector<int>>& key){
    int temp[42][42];
    for(int i=0;i<keys;i++){
        for(int j=0;j<keys;j++){
            temp[i][j] = key[i][j];
        }
    }

    for(int i=0;i<keys;i++){
        for(int j=0;j<keys;j++){
            key[i][j] = temp[j][keys-i-1];
        }
    }
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    keys = key.size();
    locks = lock.size();

    vector<vector<int>> background(2*keys+locks,vector<int>(2*keys+locks));

    for(int i=keys;i<locks+keys;i++){
        for(int j=keys;j<locks+keys;j++){
            background[i][j] = lock[i-keys][j-keys];
        }    
    }

    for(int k=0;k<4;k++){
        for(int i=0;i<keys+locks;i++){
            for(int j=0;j<keys+locks;j++){
                if(check(background, key,i,j)){
                    answer  = true;
                    return answer;
                }
            }
        }
        rotate(key);
    }
    return answer;

}