Programmers - 자물쇠와 열쇠(C++)

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

풀이

자물쇠 크기 재할당 (2 x (열쇠크기-1) + 자물쇠크기) x (2 x (열쇠크기-1) + 자물쇠크기) 후 정중앙에 자물쇠 값 할당

재할당된 자물쇠에서 한칸씩이동, 90회전으로 모든 경우의 수를 탐색

  - 열쇠의 사이즈만큼 자물쇠 배열에 + 연산

  - 실제 자물쇠의 영역을 확인 -> 값이 1이 아니라면 return false

  - returen false로 빠져나가는 것이 없다면 return true

 

#include <vector>

using namespace std;
int lockSize;
int keySize;
int len;

bool check(int y, int x, vector<vector<int>> key, vector<vector<int>> lock) {
    for(int i=y;i<y+keySize;i++){
        for(int j=x;j<x+keySize;j++){
            lock[i][j]+=key[i-y][j-x];//자물쇠값에 열쇠값을 더함
        }        
    }
    for(int i=keySize-1;i<=len-keySize;i++){
        for(int j=keySize-1;j<=len-keySize;j++){
        	//자물쇠 영역을 확인 값이 1이 아니라면 돌기와 홈이 일치하지 않으므로 false
            if(lock[i][j]!=1)return false;
        }
    }
    return true;
}

void rotate(vector<vector<int>>& key) { //시계방향 90도 회전
    vector<vector<int>> temp(keySize, vector<int>(keySize));
    for (int i = 0; i < keySize; i++) {
        for (int j = 0; j < keySize; j++) {
            temp[j][keySize - i - 1] = key[i][j];
        }
    }
    key = temp;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    lockSize = lock.size();
    keySize = key.size();
    //다시 할당할 자물쇠 크기를 
    len = 2 * (keySize - 1) + lockSize;

	//자물쇠 크기를 바꾸고 정중앙에 원래 자물쇠 값 할당
    vector<vector<int>> temp(len, vector<int>(len));
    for (int i = 0; i < lockSize; i++) {
        for (int j = 0; j < lockSize; j++) {
            temp[keySize - 1 + i][keySize - 1 + j] = lock[i][j];
        }
    }
    lock = temp;


    for (int i = 0; i <=len-keySize ; i++) {
        for (int j = 0; j <= len - keySize; j++) {
            for (int _ = 0; _ < 4; _++) { //90도 회전씩 360도 확인
                if (check(i, j, key, lock))return true;
                rotate(key);
            }
        }
    }
    return false;
}