[Programmers] 60059번 - 자물쇠와 열쇠 [Java][C++]

문제 링크

---

1. 아이디어

열쇠를 4방향(0°/90°/180°/270°)으로 회전시키며, 자물쇠 범위를 벗어나는 위치까지 포함해 가능한 모든 위치에 겹쳐본다. 겹친 결과 자물쇠 칸이 전부 정확히 1이 되면(홈과 돌기가 정확히 맞물리면) 열 수 있다고 판단했다. 범위를 벗어나는 열쇠 칸은 애초에 자물쇠 검사 대상이 아니므로 무시하면 된다.

---

2. 복잡도

시간복잡도	공간복잡도
$O((N+M)^2 (N^2+M^2))$	$O(M^2)$

$N$ = lock 한 변 길이, $M$ = key 한 변 길이 ($M \le N$)

---

3. 코드

풀이 [Java][C++]

class Solution {

    static int n, m;

    public boolean solution(int[][] key, int[][] lock) {
        n = lock.length;
        m = key.length;

        for (int d = 0; d < 4; d++) {
            for (int i = -m + 1; i < n; i++) {
                for (int j = -m + 1; j < n; j++) {
                    attach(lock, key, i, j);
                    if (match(lock)) return true;
                    detach(lock, key, i, j);
                }
            }

            key = rotate(key);
        }

        return false;
    }

    static int[][] rotate(int[][] key) {
        int[][] res = new int[m][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                res[i][j] = key[m - 1 - j][i];
            }
        }

        return res;
    }

    static void attach(int[][] lock, int[][] key, int sr, int sc) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (sr + i < 0 || sr + i >= n || sc + j < 0 || sc + j >= n) continue;
                lock[sr + i][sc + j] += key[i][j];
            }
        }
    }

    static void detach(int[][] lock, int[][] key, int sr, int sc) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (sr + i < 0 || sr + i >= n || sc + j < 0 || sc + j >= n) continue;
                lock[sr + i][sc + j] -= key[i][j];
            }
        }
    }

    static boolean match(int[][] lock) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (lock[i][j] != 1) return false;
            }
        }

        return true;
    }
}

#include <vector>

using namespace std;

int n, m;

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

    return res;
}

void attach(vector<vector<int>>& lock, vector<vector<int>>& key, int sr, int sc) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (sr + i < 0 || sr + i >= n || sc + j < 0 || sc + j >= n) continue;
            lock[sr + i][sc + j] += key[i][j];
        }
    }
}

void detach(vector<vector<int>>& lock, vector<vector<int>>& key, int sr, int sc) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (sr + i < 0 || sr + i >= n || sc + j < 0 || sc + j >= n) continue;
            lock[sr + i][sc + j] -= key[i][j];
        }
    }
}

bool match(vector<vector<int>>& lock) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (lock[i][j] != 1) return false;
        }
    }

    return true;
}

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

    for (int d = 0; d < 4; d++) {
        for (int i = -m + 1; i < n; i++) {
            for (int j = -m + 1; j < n; j++) {
                attach(lock, key, i, j);
                if (match(lock)) return true;
                detach(lock, key, i, j);
            }
        }

        key = rotate(key);
    }

    return false;
}

---