자물쇠와 열쇠

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

2020 KAKAO BLIND RECRUITMENT

시계 방향 90도 회전, 상하좌우 모두

함수로 구현하였고, 각각에 대하여 백트래킹으로 구현하였다.

하지만 계속 시간 초과 및 종료 조건(회전에 대한 인덱스, 상하좌우에 대한 인덱스의 처리를 어떻게 해야할지)을

잘 몰랐다.

그러다가, tech kakao 홈페이지에서 해설을 보았는데,

실질적으로 변환 관련 함수에서는 시계 방향 90도 회전만 구현해주고,

나머지는 lock의 size를 3배로 늘리고, 정 가운데에 lock를 오도록 새로운 Lock vector을 구하면 풀린다.

Lock vector의 (0, 0)부터 차례대로 비교해간다.

이 때, 정 가운데에 있는 lock vector을 항사 신경쓰면서, 인덱스에 대한 처리를 잘 해야한다.(check 함수)

i, j, r, c를 잘 활용해야한다.(check 함수)

#include <bits/stdc++.h>
 
using namespace std;
 
int key_size, lock_size, sy, sx, ey, ex;
vector<vector<int> > Lock;
 
vector<vector<int> > rotate(vector<vector<int> > key)
{
    vector<vector<int> > ret;
 
    for (int j = 0; j < key_size; j++)
    {
        vector<int> temp;
        for (int i = key_size - 1; i >= 0; i--) temp.push_back(key[i][j]);
        ret.push_back(temp);
    }
 
    return ret;
}
 
vector<vector<int> > magnify(vector<vector<int> > lock)
{
    vector<vector<int> > ret;
    int r = 0, c = 0;
 
    for (int i = 0; i < 3 * lock_size; i++)
    {
        vector<int> temp;
 
        for (int j = 0; j < 3 * lock_size; j++)
            if (lock_size <= i && i < 2 * lock_size && lock_size <= j && j < 2 * lock_size)
            {
                temp.push_back(lock[r][c]); ++c;
                if (c == lock_size) c = 0, ++r;
            }
            else temp.push_back(0);    
 
        ret.push_back(temp);
    }
 
    return ret;
}
 
bool check(vector<vector<int> > key, int y, int x)
{
    int r = 0, c = 0;
    vector<vector<int> > temp = Lock;
 
    for (int i = y; i < y + key_size; i++)
        for (int j = x; j < x + key_size; j++)
        {
            if (sy <= i && i <= ey && sx <= j && j <= ex)
            {
                if (!temp[i][j] && key[r][c]) temp[i][j] = 1;
                else if (temp[i][j] && key[r][c]) return false;
            }
            ++c;
            if (c == key_size) c = 0, ++r;
        }
    
    for (int i = sy; i <= ey; i++)
        for (int j = sx; j <= ex; j++)    
            if (!temp[i][j]) return false;
 
    return true;
}
 
bool solution(vector<vector<int> > key, vector<vector<int> > lock) 
{
    key_size = key.size();
    lock_size = lock.size();
    Lock = magnify(lock);
 
    sy = sx = lock_size;
    ey = ex = 2 * lock_size - 1;
 
    for (int d = 0; d < 4; d++)
    {
        key = rotate(key);
 
        for (int i = 0; i <= Lock.size() - key_size; i++)
            for (int j = 0; j <= Lock.size() - key_size; j++)    
                if (check(key, i, j))
                    return true;            
    }
 
    return false;
}
 
int main(void)
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    vector<vector<int> > key = {
        {0, 0, 0},
        {1, 0, 0},
        {0, 1, 1}
    };
 
    vector<vector<int> > lock = {
        {1, 1, 1},
        {1, 1, 0},
        {1, 0, 1}
    };
 
    cout << solution(key, lock) << '\n';
 
    return 0;
}