[프로그래머스] 2020 KAKAO BLIND RECRUITMENT : 자물쇠와 열쇠 (C++)

문제 링크 : 자물쇠와 열쇠

[문제 접근]

제한사항이 작은거로 보아서 자물쇠와 맞닿는 부분이 최소일 때까지 전부 탐색해도 가능하다.

⭐️ 탐색 범위

이런식으로 전체 arr크기를 최대 범위로 넓혀서 탐색하면되는데 어차피 탐색시 시작점만 구해서 탐색하면되므로 (key의 size)+(lock의 size)-1 까지 탐색하면 된다.

⭐️ 탐색 방법

먼저 arr배열을 초기화해주는데 초기화시에는 arr배열의 가운데에 lock의 값을 할당해준다.
그리고 key의 값들을 스타트 지점에 맞춰서 arr배열에 넣어준다.
예를 들어 위 그림과 같이 스타트 지점이 (1, 1)인 상태면 저렇게 겹친 상태가 된다.

⭐️ key 회전

탐색시 key를 이동하기 전에 회전했을 때의 경우도 전부 시도해본다. 4번 회전하게되면 원래 상태로 돌아오기 때문에 총 회전을 4번해주어서 시도하면 된다.

회전시에는 규칙이 있는데 key의 크기가 4라고 가정하면 하나씩 해보면
(0, 0)자리에 (3, 0)자리에 있는 값이 온다.
(0, 1)자리에 (2, 0)자리에 있는 값이 온다.
즉, (i, j)자리에는 (key의size-1-j, i) 자리에 있는 값이 오는 규칙을 발견할 수 있다.

소스코드 상의 주석을 잘 따라가보면 쉽게 이해할 수 있다.

[소스 코드]

#include <string>
#include <vector>
#include <cstring>

using namespace std;
int arr[60][60];
int ksize = 0;
int lsize = 0;

void makeinit(vector<vector<int>> lock) {
    memset(arr, 0, sizeof(arr));
    int start = ksize-1;
    int end = start+lsize;
    
    for(int i=start ; i<end ; i++) {
        for(int j=start ; j<end ; j++) {
            arr[i][j] = lock[i-start][j-start];
        }
    }
}

void printKey(vector<vector<int>> key, int y, int x) {
    int size = key.size();
    for(int i=y ; i<y+size ; i++) {
        for(int j=x ; j<x+size ; j++) {
            arr[i][j] += key[i-y][j-x];
        }
    }
}

bool checkLock() {
    int start = ksize-1;
    int end = start+lsize;
    
    for(int i=start ; i<end ; i++) {
        for(int j=start ; j<end ; j++) {
            if(arr[i][j]!=1) return false;
        }
    }
    
    return true;
}

bool checkKey(vector<vector<int>> key, int y, int x) {
    printKey(key, y, x); // 현재 key를 arr배열에 대입
    return checkLock(); // 자물쇠가 전부 1로 되어있는지 검사
}

vector<vector<int>> spinKey(vector<vector<int>> key) {
    vector<vector<int>> result;
    
    for(int i=0 ; i<ksize ; i++) {
        vector<int> temp;
        for(int j=0 ; j<ksize ; j++) {
            temp.push_back(key[ksize-j-1][i]);
        }
        result.push_back(temp);
    }
    
    return result;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    ksize = key.size();
    lsize = lock.size();
    int end = key.size()+lock.size()-1; // 탐색해야하는 지점의 끝

    for(int i=0 ; i<end ; i++) { 
        for(int j=0 ; j<end; j++) { // key 스타트 지점
            for(int k=0 ; k<4 ; k++) { // 4번 회전하면 원래 key로 돌아옴
                makeinit(lock); // 전체 배열 초기화
                if(checkKey(key, i, j)) { // key를 대입해서 lock이 풀리는지 검사
                    return true;
                } else {
                    key = spinKey(key); // key를 시계방향으로 회전
                }
            }
        }
    }
    
    return false;
}