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

저번에 풀었던 짠돌이 호석과 같은 방법으로 접근했습니다.

lock을 가운데에 놔두고 key를 4방향으로 돌려가며 모두 탐색했습니다.

map의 크기는 N + 2M이면 될 것 같아 N + 2M으로 설정했습니다. 

지난번과는 조금 다르게 check를 하는 부분에서 값을 더하고 check하고 빼주면서 확인했습니다.

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

int N,M;
vector<vector<int>> map, key, lock;
bool answer;

void rotate(vector<vector<int>>& key){
    vector<vector<int>> temp(M,vector<int>(M));
    for(int i = 0; i<M; i++){
        for(int j = 0; j<M; j++){   
            temp[i][j] = key[j][M-i-1];
        }
    }
    for(int i = 0; i<M; i++){
        for(int j = 0; j<M; j++){
            key[i][j] = temp[i][j];
        }
    }
}

bool check(vector<vector<int>>& key, int x, int y){
    bool check = true;
    for(int i=y; i<y+M; i++){ //map에 적용
        for(int j = x; j<x+M; j++){
            map[i][j]+=key[i-y][j-x];
        }
    }
    
    for(int i=M; i<M+N; i++){   
        for(int j = M; j<M+N; j++){
            if(map[i][j]!=1){
                check = false;
                break;
            }
        }
        if(check == false)break;
    }
    
    for(int i =y; i<y+M; i++){  //map에 적용한거 되돌리기
        for(int j = x; j<x+M; j++){
            map[i][j] -= key[i-y][j-x];
        }
    }
    return check;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    M = key.size();
    N = lock.size();
    map = vector<vector<int>> (2*M + N, vector<int>(2*M + N));
    for(int i = M; i< N+M; i++){    //map 가운데에다가 lock 위치시킨다
        for(int j = M; j<M+N; j++){
            map[i][j] = lock[i-M][j-M];
        }
    }
    for(int i = 0; i< M+N; i++){    //0부터 M+N 까지 모두 탐색
        for(int j = 0; j< M+N; j++){
            for(int k = 0; k < 4; k++){ //회전시켜가며 확인하다가 true면 리턴
                rotate(key);
                if(check(key, i,j)){
                    answer = true;
                    break;
                }
            }
            if(answer)break;
        }
        if(answer) break;
    }
    
    return answer;
}