📚 Lv3 - 자물쇠와 열쇠

자물소와 열쇠

 

📖 A. 문제 이해

자물쇠 크기 : N x N
열쇠 크기 : M x M

M <= N

일 때, 열쇠를 돌려가면서 자물쇠를 모두 1로 만들 수 (열쇠로 자물쇠를 열 수) 있다면 true
자물쇠를 모두 1로 만들 수 없다면 false
이다.

ex) 열쇠를 90도씩 회전해가면서 맞추었을 때 자물쇠 결과가 이와 같다면

1	1	1		1	1	1
1	1	1		1	0	1
1	1	1		1	1	1

• true, false이다.

 

✔️ 어떻게 풀어야할까?

swexpert에서 비슷한 문제를 푼 기억이 있다.

자물쇠 돌기와 열쇠 돌기가 하나가 겹치는 부분부터 검색을 시작한다.

0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	1	1	1	0	0
0	0	1	1	0	0	0
0	0	1	0	1	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

이와 같이 있을 때

첫 번째로 (1, 1)부터 열쇠 돌기를 채운다면

0	0	0	0	0	0	0
1	0	0	0	0	0	0
0	1	2	1	1	0	0
0	0	1	1	0	0	0
0	0	1	0	1	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

(3, 3)에서 하나가 겹치는 것을 알 수 있다.
자물쇠 돌기 부분이 모두 1이 아니므로 x이다.

다음차례에서 열쇠는 회전 및 이동이 가능하므로 회전일 경우 (90, 180, 270)도가 가능하다.

90도 회전할 경우

0	1	0	0	0	0	0
1	0	0	0	0	0	0
1	0	1	1	1	0	0
0	0	1	1	0	0	0
0	0	1	0	1	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

이와 같고, 자물쇠 돌기 부분이 모두 1이 아니므로 x이다.

~

0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	1	1	1	0	0
0	0	1	1	1	0	0
0	0	1	1	1	0	0
0	0	0	1	0	0	0
0	0	0	0	0	0	0

3, 3에서 90도 회전할 경우 자물쇠 돌기 부분을 모두 1로 맞출 수 있다.

그러므로 true이다.

이걸 생각해서 구현하면 된다.

 

 

📖 B. 소스

class Solution {  
    static int N, M;  
    static int[][] rectan, copyrecTan;  
    static int rectanLen;  
    static int[][][] recGame;  
  
    // 현재 체크한 자물쇠에 1이 아닌 것이 있다면, 열 수 없다!  
    boolean checkRectangle() {  
        for (int i = M - 1; i < M - 1 + N; i++) {  
            for (int j = M - 1; j < M - 1 + N; j++) {  
                if (copyrecTan[i][j] != 1) return false;  
            }  
        }  
        return true;  
    }  
  
    public boolean solution(int[][] key, int[][] lock) {  
        boolean answer = false;  
  
        M = key.length;  
        N = lock.length;  
  
        // 자물쇠의 크기를 늘린다.  
        rectanLen = 2 * (M - 1) + N;  
        rectan = new int[rectanLen][rectanLen];  
        copyrecTan = new int[rectanLen][rectanLen];  
        recGame = new int[4][M][M];  
  
  
        // 시작 전 lock 저장  
        for (int i = M - 1; i < M - 1 + N; i++) {  
            for (int j = M - 1; j < M - 1 + N; j++) {  
                rectan[i][j] = lock[i - (M - 1)][j - (M - 1)];  
            }  
        }  
  
        recGame[0] = key;  
  
        // 90, 180, 270 회전 저장  
        for (int i = 1; i < 4; i++) {  
            for (int k = 0; k < M; k++) {  
                for (int k2 = 0; k2 < M; k2++) {  
                    recGame[i][k][k2] = recGame[i - 1][M - k2 - 1][k];  
                }  
            }  
        }  
  
        // 첫 열쇠의 마지막 행열 위치 M-1, M-1부터 2 * (M - 1) + N; 까지 반복문을 돌린다.  
        Loop:  
        for (int i = M - 1; i < rectanLen; i++) {  
            for (int j = M - 1; j < rectanLen; j++) {  
  
                // 회전 : 0, 90, 180, 270                
                for (int r = 0; r < 4; r++) {  
                    // 결과를 저장할 배열  
                    copyrecTan = rectan;  
  
                    // 자물쇠 돌기에 열쇠 돌기를 넣는다.  
                    for (int k = 0; k <= M - 1; k++) {  
                        for (int k2 = 0; k2 <= M - 1; k2++) {  
                            copyrecTan[i - (M - 1) + k][j - (M - 1) + k2] += recGame[r][k][k2];  
                        }  
                    }  
  
                    // 모두 1인지 검사한다.  
                    if (checkRectangle()) {  
                        answer = true;  
                        break Loop;  
                    }  
  
                    // 자물쇠 돌기에 넣었던 열쇠 돌기를 뺀다.  
                    for (int k = 0; k <= M - 1; k++) {  
                        for (int k2 = 0; k2 <= M - 1; k2++) {  
                            copyrecTan[i - (M - 1) + k][j - (M - 1) + k2] -= recGame[r][k][k2];  
                        }  
                    }  
                }  
            }  
        }  
  
        return answer;  
    }  
}