[Algorithm] Programmers :: 자물쇠와 열쇠

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

프로그래머스

int keySize, lockSize, newSize;
int newLock[70][70];
vector<vector<vector<int>>> rotateMatrixes;
int keyMoveMaxCount = 0;
int targetCount = 0;
 
bool check(int offsetY, int offsetX)
{
    for (int i = 0; i < 4; ++i)
    {
        bool isBreak = false;
        int count = 0;
 
        for (int j = 0; j < keySize; ++j)
        {
            for (int k = 0; k < keySize; ++k)
            {
                int keyValue = rotateMatrixes[i][j][k];
                int mappingedValue = newLock[j + offsetY][k + offsetX];
 
                if (keyValue == mappingedValue) // 둘 다 비어있거나, 메워져있거나
                {
                    isBreak = true;
                    break;
                }
                else if (keyValue == 1 && mappingedValue == 0) // 적절하면
                {
                    ++count;
                }
            }
 
            if (isBreak) break;
        }
 
        if (!isBreak && count == targetCount)
        {
            return true;
        }
    }
 
    return false;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) 
{
    keySize = key.size();
    lockSize = lock.size();
    newSize = lockSize + (keySize - 1) * 2;
    keyMoveMaxCount = newSize - keySize + 1;
 
    memset(newLock, 0x3f, sizeof(newLock));
 
    for (int i = 0; i < lockSize; ++i)
    {
        for (int j = 0; j < lockSize; ++j)
        {
            newLock[i + keySize - 1][j + keySize - 1] = lock[i][j];
            if (lock[i][j] == 0) ++targetCount;
        }
    }
 
    rotateMatrixes.resize(4, vector<vector<int>>(keySize, vector<int>(keySize)));
    rotateMatrixes[0] = key;
 
    for (int i = 1; i < 4; ++i)
    {
        for (int j = 0; j < keySize; ++j)
        {
            for (int k = 0; k < keySize; ++k)
            {
                rotateMatrixes[i][j][k] = rotateMatrixes[i - 1][keySize - 1 - k][j];
            }
        }
    }
 
    for (int i = 0; i < keyMoveMaxCount; ++i)
    {
        for (int j = 0; j < keyMoveMaxCount; ++j)
        {
            if (check(i,j))
            {
                return true;
            }
        }
    }
 
    return false;
}

다른 사람의 아이디어를 참고하였는데, 친절한 설명글은 다음과 같다.

https://yabmoons.tistory.com/678

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

 

크기를 늘린 새로운판에서 체크한다는 아이디어만 참고하고, 직접 생각을 확장시켜서 코드를 작성했다.

검사할때마다 회전할 필요가 전혀 없기때문에 rotateMatrixes라는 룩업테이블을 따로 만들었다. 즉 90도,180도,270도,360도 회전에 대한 key의 형태를 전부 rotateMatrixes에다가 저장해놨다.

이후 0,0부터 keyMoveMaxCount,keyMoveMaxCount 까지 룩업테이블의 키좌표와 newLock의 좌표를 비교하면 된다.

룩업테이블의 좌표는 그냥 key의 좌표니까 newLock의 좌표로 매핑시켜서 비교해야 한다.

 

비교할때는 서로 같은값이면 해당회전일때의 비교는 바로 종료시킨다. 즉 키의 빈부분과 자물쇠의 빈부분, 혹은 키의 돌출부분과 자물쇠의 돌출부분일 경우 바로 종료시킨다.

오로지 자물쇠의 빈부분, 키의 돌출부분일때만 ++count를 하고, 해당 키의회전형태일 때의 검사를 마쳤는데 isBreak == false이고 (적절하지않았던 적이 없다면), count가 maxCount와 일치한다면 (자물쇠의 빈 부분이 모두 메꿔졌다면) true를 리턴하고 모든 과정을 종료한다.

 

룩업테이블을 안하더라도 key와 lock의 크기가 작기때문에 효율성에서 걸릴 것 같진 않지만, 미리미리 챙길 수 있는부분은 챙기는 연습을 하는게 좋을 것 같아서 룩업테이블을 이용했다.