프로그래머스 - 자물쇠와 열쇠 (Lv.3) (2차원 배열 시계방향회전, 맵 확장 + 탐색방법 기억)

문제 링크

• 👉 자물쇠와 열쇠

문제 설명

• 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
• 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다.
• 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다.
• 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다.
• 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
• 열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

문제 접근

• 열쇠는 회전이 가능하다. 열쇠가 자물쇠 영역을 벗어나는 것은 영향을 주지 않는다. 라는 조건을 확인하고, 완전탐색을 해야겠다고 생각했다.
• 핵심은 열쇠를 자물쇠에 어떻게 대입을 할 것인지인데 이 과정에서 자물쇠 맵을 확장하는 생각을 했다. 예제처럼 열쇠의 크기가 3x3, 자물쇠의 크기가 3x3 인 경우 자물쇠의 크기를 7x7 로 확장하여 열쇠의 우측 하단 칸부터 대입 가능한 모든 경우로 움직일 수 있도록 하는 것이다.
• 이때, 실제 자물쇠의 시작좌표는 (m-1, m-1) 이다.
• 실제 자물쇠 영역이 모두 1로 가득차게 된다면 탐색을 중단한다.

구현

#include <string>
#include <vector>
#include <iostream>

using namespace std;

void RotateKey(vector<vector<int>>& key)
{
    int m = key.size();
    vector<vector<int>> rotatedKey;
    for(int c=0; c<m; c++)
    {
        vector<int> line;
        for(int r=m-1; r>=0; r--)
        {
            line.push_back(key[r][c]);
        }
        rotatedKey.push_back(line);
    }
    key = rotatedKey;
}

// 자물쇠를 확장한다.
void ExpandLock(vector<vector<int>>& lock, int keySize)
{
    int n = lock.size();
    int exN = n + (keySize-1) * 2;
    vector<vector<int>> exLock(exN, vector<int>(exN,0));
    for(int r=0; r<n; r++)
    {
        for(int c=0; c<n; c++)
        {
            exLock[keySize-1+r][keySize-1+c] = lock[r][c];
        }
    }
    
    lock = exLock;
}

void PutKeyOnLock(vector<vector<int>>& key, vector<vector<int>>& lock, int x, int y)
{
    int m = key.size();
    for(int r=0; r<m; r++)
    {
        for(int c=0; c<m; c++)
        {
            lock[x+r][y+c] += key[r][c];
        }
    }
}

bool IsOpened(vector<vector<int>>& lock, int n, int m)
{
    for(int r=0; r<n; r++)
    {
        for(int c=0; c<n; c++)
        {
            if(lock[r+m-1][c+m-1] != 1) return false;
        }
    }
    return true;
}

bool IsKeyOpenLock(vector<vector<int>>& key, vector<vector<int>>& lock, int n)
{
    vector<vector<int>> tmpLock;
    int limit = lock.size() - (key.size() - 1);
    for(int r=0; r<limit; r++)
    {
        for(int c=0; c<limit; c++)
        {
            tmpLock = lock;
            PutKeyOnLock(key, tmpLock, r, c);
            if(IsOpened(tmpLock, n, key.size()) == true) return true;
        }
    }
    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int n = lock.size();
    ExpandLock(lock, key.size());
    for(int i=0; i<4; i++)
    {
        if(IsKeyOpenLock(key, lock, n)==true) return true;
        RotateKey(key);
    }
    return false;
}