2020 Kakao blind 60059 - 자물쇠와 열쇠(완전탐색, 배열) c++

- key와 lock의 사이즈 조건이 20이하이므로 모든 조건에 대해서 키를 돌려가면서 매칭시켜서 lock이 열리는 조건이 발견되면 1를 리턴해주는 로직을 짜면 된다.

- lock의 row, col 범위를 2 * key 사이즈 + lock사이즈으로 늘린 다음에 가운데에 원래 lock의 값을 넣어주고 탐색을 하면 key와 lock이 겹치는 조건을 생각하기가 더 쉬워진다. 탐색시에 lock과 key가 겹쳐지지 않는 케이스가 생기지만 탐색범위가 20 by 20이기 때문에 크게 시간이 늘어나지 않는다.

#include <vector>
using namespace std;

int m, n;
vector<vector<int>> Lock, Lock_cpy, Key;

void rotate() {
    vector<vector<int>> tmp(m, vector<int>(m));
    for(int i = 0; i < m; ++i) {
        for(int j = 0; j < m; ++j) {
            tmp[i][j] = Key[j][m - i - 1];
        }
    }
    
    Key = tmp;
}

bool unlock(int r, int c) {
    for(int i = r; i < r + m; ++i) {
        for(int j = c; j < c + m; ++j) {
            Lock[i][j] += Key[i - r][j - c];
        }
    }
    
    for(int i = m; i < m + n; ++i) {
        for(int j = m; j < m + n; ++j) {
            if(Lock[i][j] != 1) {
                return false;
            }
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    m = key.size(), n = lock.size();
    Lock.resize(2 * m + n - 2, vector<int>(2 * m + n - 2));
    
    for(int i = m, r = 0; i < m + n; ++i, ++r) {
        for(int j = m, c = 0; j < m + n; ++j, ++c) {
            Lock[i][j] = lock[r][c];
        }
    }
    Lock_cpy = Lock;
    Key = key;
    
    for(int i = 0; i < m + n; ++i) {
        for(int j = 0; j < m + n; ++j) {
            for(int k = 0; k < 4; ++k) {
                rotate();
                if(unlock(i, j)) {
                    return true;
                }
                Lock = Lock_cpy;
            }
        }
    }
    
    return false;
}

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

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