[프로그래머스] 자물쇠와 열쇠(C++)

자물쇠와 열쇠 (Level 3)

문제

전체 문제 보기

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

접근법

이번 문제는 주어진 제한이 크지 않기 때문에 완전 탐색을 통해서 해결할 수 있습니다. 자물쇠 배열의 크기보다 3배 큰 새로운 자물쇠 배열을 만든 뒤 열쇠를 모든 위치에 대입시켜보면서 계산하여 답을 구할 수 있습니다.

이때 열쇠는 회전시켜 적용할 수 있기 때문에 key 배열을 90도 회전하는 함수 Rotate90을 다음과 같이 구현하였습니다.

void Rotate90(Mat& arr)
{
    vector<vector<int>> temp = arr;
    const int n = temp.size() - 1; 
    for(int r = 0 ; r < arr.size(); r++)
        for(int c = 0; c < arr.size(); c++)
            arr[r][c] = temp[n-c][r];
}

실행 결과

lock의 한변의 크기 n에 대해서 4중 반복문을 사용하고 있기 때문에 \(O(n^4)\) 알고리즘이지만, n의 최댓값이 20이기 때문에 충분히 시간 내에 계산이 가능했습니다.

전체 구현

아래와 같이 구현할 수 있습니다.

#include <vector>
using namespace std;
using Mat = vector<vector<int>>;

void Rotate90(Mat& arr)
{
    vector<vector<int>> temp = arr;
    const int n = temp.size() - 1; 
    for(int r = 0 ; r < arr.size(); r++)
        for(int c = 0; c < arr.size(); c++)
            arr[r][c] = temp[n-c][r];
}

bool CheckByPos(int off_r, int off_c, const Mat& key, Mat& resize_lock )
{
    for(int r = 0; r < key.size(); ++r)
        for(int c = 0; c < key.size(); ++c)
            resize_lock[r + off_r][c + off_c] += key[r][c];

    bool result = true;

    const int N = resize_lock.size() / 3;
    for(int r = N; r < N * 2; ++r)
        for(int c = N; c < N * 2; ++c)
            if(resize_lock[r][c] != 1) 
                result = false;

    for(int r = 0; r < key.size(); ++r)
        for(int c = 0; c < key.size(); ++c)
            resize_lock[r + off_r][c + off_c] -= key[r][c];

    return result;
}

bool Check(const Mat& key, Mat& resize_lock)
{
    const int N = resize_lock.size() / 3;
    for(int r = 0; r < N * 2; ++r)
        for(int c = 0; c < N * 2; ++c)
            if(CheckByPos(r,c,key, resize_lock) == true)
                return true;
    return false;

}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    const int N = lock.size();
    Mat resize_lock(lock.size() * 3, vector<int>(lock.size() * 3));
    for(int r = N; r < 2 * N; ++r)
    {
        for(int c = N; c < 2 * N; ++c)
        {
            resize_lock[r][c] = lock[r-N][c-N];
        }
    }
    for(int i = 0; i < 4; ++i)
    {
        if(Check(key, resize_lock) == true)
        {
            answer = true;
            break;
        }
        Rotate90(key);
    }
    return answer;
}