프로그래머스 문제 - 자물쇠와 열쇠

프로그래머스 자물쇠와 열쇠 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 자물쇠가 열립니다.
자물쇠 영역을 벗어난 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않습니다.
자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 가지고 자물쇠를 열 수 있는지 확인해야 합니다.

문제 풀이

열쇠와 자물쇠는 최대 20칸으로 모든 경우의 수 체크가 가능할 정도의 칸 수입니다.

열쇠는 회전이 가능하기 때문에 90도씩 3번 돌려 총 4가지의 열쇠 모양을 가질 수 있습니다.
또한 이동이 가능하고 자물쇠 크기만큼 비교하기 위해 왼,오,위,아래 전부 자물쇠 범위만큼 벗어날 수 있기 때문에 주어진 key배열 사방을 lock범위만큼 추가로 확장시켜 줍니다.
이후에 왼쪽 위 한칸씩부터 오른쪽 아래까지 key의 배열 내 원소가 lock범위에 걸치는 모든 경우의 수를 확인해주면 됩니다.

여기서 주의할 점은 key배열과 lock의 배열의 크기가 다를 수 있다는 점이기에 잘 생각해서 경우의 수를 찾아주어야 합니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int keySize;
int lockSize;
bool answer;
vector<vector<int>> keyTile;
vector<vector<int>> lockTile;

void solve(int startX, int startY)
{
    //자물쇠 사이즈만큼 비교하여 열쇠가 맞는지 확인
    for(int i = startX; i < startX + lockSize; i++)
    {
        for(int j = startY; j < startY + lockSize; j++)
        {
            if(keyTile[i][j] != lockTile[i - startX][j - startY])
            {
                return;
            }
        }
    }
    answer = true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    answer = false;
    keySize = key.size();
    lockSize = lock.size();
    lockTile = lock;
    //열쇠크기 주변에 자물쇠 크기만큼 추가로 배열을 늘려줌
    keyTile.assign(lockSize*2+keySize, vector<int>(lockSize*2+keySize, 0));
    
    //자물쇠와 열쇠를 더 좋게 맞추기 위해 0과 1을 바꿔줌
    for(int i = 0; i < lockSize; i++)
    {
        for(int j = 0; j < lockSize; j++)
        {
            if(lockTile[i][j] == 1)
                lockTile[i][j] = 0;
            else
                lockTile[i][j] = 1;
        }
    }
    //열쇠 사이즈 입력
    for(int i = 0; i < keySize; i++)
    {
        for(int j = 0; j < keySize; j++)
        {
            keyTile[i+lockSize][j+lockSize] = key[i][j];
        }
    }
    
    //90도씩 돌려가며 열쇠 모양 찾기
    for(int k = 0; k < 4; k++)
    {
        for(int i = 1; i < keySize+lockSize; i++)
        {
            for(int j = 1; j < keySize+lockSize; j++)
            {
                solve(i, j);
                if(answer)
                {
                    return answer;
                }
            }
        }
        //열쇠 90도 돌리기
        vector<vector<int>> temp = keyTile;
        for(int i = 0; i < lockSize*2+keySize; i++)
        {
            for(int j = 0; j < lockSize*2+keySize; j++)
            {
                keyTile[i][j] = temp[lockSize*2+keySize-1-j][i];
            }
        }
    }
    
    return answer;
}

출저

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