3번 포스팅을 시작하겠습니다. 3번부터 정답률이 갑자기 7%로 떨어지면서 고난이도 문제임을 보여주고 있습니다. 확실히 문제도 쉬워보이지는 않습니다. 문제의 핵심을 파악하자면 열쇠를 이용해서 자물쇠를 열 수 있는지 판별하는 문제인데, 열쇠는 자물쇠보다 크기가 작거나 같으며 90도씩 회전하며 끼워볼 수 있는 형태로 되어 있으며, 돌기끼리는 서로 맞닿을 수 없고, 자물쇠의 모든 빈칸을 채울 수 있으면 true, 그렇지 않으면 false를 리턴하면 됩니다.
열쇠가 자물쇠보다 작을 수 있기 때문에 함정에 빠지지 않아야할 부분은, 모든 빈칸을 다 채울 수 있는지를 반드시 체크해야 된다는 점입니다. 그렇기 때문에 for문을 돌려 열쇠가 모든 자물쇠 구멍을 다 채운다 하더라도, 열쇠 바깥 구멍이 남아있다면 자물쇠를 풀 수 없으므로 미리 빈칸의 개수를 세어 두는 과정이 필요합니다.
다음으로 특정 방향에서 열쇠로 자물쇠를 풀 수 없을 경우 자물쇠를 회전시켜야 하는데, 회전을 시키는 방법은 다음과 같이 배열을 재지정 해주면됩니다. 키는 정사각형이라고 하였으므로 한 변의 길이를 $K$라고 할 때
$$nextkey[x][y] = prevkey[K-y-1][x] (0<=x<K, 0<=y<K)$$
로 지정할 경우 시계방향으로 90도 돌아간 것과 같은 효과를 보이게 됩니다. 만약 이해가 되지 않는다면 직접 그려서 해보는 것도 좋은 방법입니다.
이제 실제로 자물쇠에 키를 대보면서 모든 빈칸을 채울 수 있는지를 확인해야 하는데, 기본적으로 $O(n^4)$ 의 복잡도를 이용해 체크할 수 있습니다. 이 때 카카오 블로그 해설에 나와있는 것처럼, 자물쇠 크기보다 3배 큰 정사각형 배열을 잡고 시작점을 자물쇠의 크기를 $L$ 이라 할 때 $-L$ ~ $2*L$ 까지 범위를 잡아 2중 for문을 돌리고, 실제 키와 자물쇠가 모두 일치하는지 확인해야 하므로 key에 대한 2중 for문을 돌려 대조를 해야 합니다. 이 때 열쇠와 자물쇠가 맞는지 확인하는 간단한 방법은 홈이 0, 돌기가 1이라고 하였을 때
$$Key[x][y] + Lock[z][w] = 1$$
을 만족하면 됨을 알 수 있습니다. 이 때 자물쇠 바깥 범위를 돌고 있다면 $Lock[z][w] = 1 - Key[x][y]$ 로 대입하여 항상 맞다고 가정을 할 수 있게 됩니다. 저같은 경우 직접 배열을 만들지 않고, 범위 바깥을 벗어났는지 검사하여 풀었습니다. 자세한 사항은 소스코드를 확인 부탁드립니다.
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
int cnt = 0, ks = key.size(), ls = lock.size();
for (int i = 0; i < ls; i++) {
for (int j = 0; j < ls; j++) {
if (lock[i][j] == 0) cnt++;
}
}
for (int i = 0; i < 4; i++) {
bool f = false;
for (int x = -ls; x < 2 * ls && !f; x++) {
for (int y = -ls; y < 2 * ls && !f; y++) {
bool g = true;
int cmp = 0;
for (int lx = x, kx = 0; kx < ks && g; lx++, kx++) {
for (int ly = y, ky = 0; ky < ks && g; ly++, ky++) {
bool over = (lx < 0 || lx >= ls || ly < 0 || ly >= ls);
int kcmp = key[kx][ky], lcmp = over ? 1 - kcmp : lock[lx][ly];
g = kcmp + lcmp == 1;
if (g && !over && lcmp == 0) cmp++;
}
}
f = g && cmp == cnt;
}
}
if (f) return true;
int tmp[20][20] = { 0 };
for (int j = 0; j < ks; j++) {
for (int k = 0; k < ks; k++) {
tmp[j][k] = key[ks - k - 1][j];
}
}
for (int j = 0; j < ks; j++) {
for (int k = 0; k < ks; k++) {
key[j][k] = tmp[j][k];
}
}
}
return false;
}