자물쇠와 열쇠

Description

문제 설명
고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
• 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

Example

key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
result = true

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

Code

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > rotate(vector<vector<int> > key, int m){
    vector<vector<int> > r_key (m, vector<int> (m, 0));
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            r_key[j][m-1-i]=key[i][j];
        }
    }
    return r_key;

}
vector<vector<int> > move(vector<vector<int> > key, int m, int direction, int l){ 
    if(l==0) // not moving
        return key;

    vector<vector<int> > m_key (m, vector<int> (m, 0));
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            switch (direction)
            {
            case 0:
                // up
                if(i < m-l)
                    m_key[i][j] = key[i+l][j];
                else m_key[i][j] = 0;
                break;
            case 1:
                // down
                if (i > l-1)
                    m_key[i][j] = key[i-l][j];
                else m_key[i][j] = 0;
                break;
            case 2:
                // left
                if(j < m-l)
                    m_key[i][j] = key[i][j+l];
                else m_key[i][j] = 0;
                break;
            case 3:
                // right
                if(j > l-1)
                    m_key[i][j] = key[i][j-l];
                else m_key[i][j] = 0;
                break;
            }
        }
    }
    return m_key;
}

bool key_compare(vector<vector<int> > padded_key, vector<vector<int> > padded_lock, int m, int n){
    for(int i=0; i<n+m-1; i++){
        for(int j=0; j<n+m-1; j++){
            if(padded_lock[i][j] == -1)
                continue;
            if(padded_lock[i][j] == 1 && padded_key[i][j] == 1)
                return false;
            if(padded_lock[i][j] == 0 && padded_key[i][j] == 0)
                return false;
        }
    }
    return true;
}

bool key_moving(vector<vector<int> > padded_key, vector<vector<int> > padded_lock, int m, int n){
    for(int i=0; i < n+m-1; i++){
        vector<vector<int> > tmp_padded_key = padded_key;
        for(int j=0; j<n+m-1; j++){
            if(key_compare(padded_key, padded_lock, m, n) == true)
                return true;
            padded_key = move(padded_key, padded_key.size(), 3, 1);
        }
        padded_key = tmp_padded_key;
        padded_key = move(padded_key, padded_key.size(), 1, 1);
    }
    return false;
}

vector<vector<int> > padding_lock(vector<vector<int> > lock, int m, int n){
    vector<vector<int> > padded_lock (n+m*2-2, vector<int> (n+m*2-2, -1));
    for(int i=m-1; i<m-1+n; i++){
        for(int j=m-1; j<m-1+n; j++){
            padded_lock[i][j] = lock[i-m+1][j-m+1];
        }
    }
    return padded_lock;
}
vector<vector<int> > padding_key(vector<vector<int> > key, int m, int n){
    vector<vector<int> > padded_key (n+m*2-2, vector<int> (n+m*2-2, 0));
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            padded_key[i][j] += key[i][j];
        }
    }
    return padded_key;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    int m = key.size();
    int n = lock.size();

    vector<vector<int> > padded_lock = padding_lock(lock, m, n);
    vector<vector<int> > padded_key = padding_key(key, m, n);
    for(int r=1; r<=4; r++){//for rotate
        vector<vector<int> > padded_key = padding_key(key, m, n);
        if(key_moving(padded_key, padded_lock, m, n) == true){
            return true;
        }
        key = rotate(key, m);
    }
    return false;
}

Thoughts

위 문제는 2020 카카오 신입 개발자 블라인드 1차 코딩테스트에서 3번 문제로 정답률이 무려 7.4%를 기록한 문제이다.
문제를 이해하려면 좀 자세히 읽어봐야한다. (처음부터 완벽히 이해하긴 좀 어려웠고 테스트케이스가 통과하지 않으면서 고려해야하는 모든 상황을 따지다보면 완전히 이해됐다)
우선 이 문제에서는 주어진 열쇠를 모든 경우를 시도해서 자물쇠에 맞는지 체크하는 것이다.
따라서 내가 새웠던 계획은

1. 0°, 90°, 180°, 270°회전을 해서 열쇠의 방향을 네가지 경우로 나눈다.
2. 자물쇠에 가능한 모든 경우를 체크해서 열쇠가 자물쇠를 열 수 있는지 여부를 체크한다

열쇠를 회전하는 것은 구현하는데 어렵지 않았으나 2번의 경우가 꽤 까다로웠고 어려웠다.

위 그림을 보면 모든 경우를 탐색하는 방법에 대한 그림인데, 자물쇠 모서리 끝부터 열쇠를 이동시키면서 생길 수 있는 모든 확인 경우를 따져줘야 한다.
가장 시간이 오래 걸렸던 부분은 그 방법을 알고 난 뒤 어떻게 구현할 것인가 이다.

각 윈도우의 값을 비교하기위에서 가장 생각하기 쉬웠던 방법은 자물쇠와 키에 일정한 크기의 길이를 더해서 차원을 맞춰준 후에 비교하는 방법이다.
키의 높이 m에서 m-1 만큼의 길이를 더해주면 padded_lock, padded_key를 같은 크기로 만들어 줄 수 있고, 그렇게 하면 자물쇠에 모든 경우의 체크를 하기 쉬워진다.
padded_lock에는 padded된 칸에는 -1을 넣어 padded_key와 비교할 때 무시 할 수 있도록 집어 넣었고, padded_key를 순회하기 편하게 move 함수를 구현해서 순회하였다.
자물쇠가 열리는 순간은, lock 의 0에 key의 1이 들어와야하고, lock의 1에는 key의 1이 나타나서 돌기끼리 맞물리면 안된다. 이 경우를 체크만 해주면, 문제를 풀 수 있다.

정리하자면, 다소 까다로운 문제의 조건을 이해하고, 모든 경우의 수를 파악하는 수학적인 생각과 이를 코드로 구현하는 능숙함만 있으면 풀 수 있었다.
(나 역시 처음에는 이게 시간 안에 가능하지 않았다.)
집중력과 연습 뿐이라는 생각을 다시 한 번 한다. 🙇🏻‍♂️