링크

문제 링크

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 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은 돌기 부분을 나타냅니다.

입출력 예

입출력 예 설명

사진 크기가 너무 커서 링크로 대체

풀이

1. lock을 확장한다. (lock.length + key.length * 2)
2. 큰 길이의 배열을 다루는게 아니기때문에 완전탐색으로 할만함을 인지하자
3. (0,0)부터 확장시킨 lock(소스코드상 ag_lock)에 key를 대보면서 key값이랑 더한다
4. 더했으면 ag_lock속 lock 범위의 값들이 모두 1인지 확인한다
5. 2(돌기끼리 더해졌거나) 또는 0(홈끼리 더한 경우)가 존재할 경우 더했던 것을 전부 되돌리고 탐색 그만
6. 4번과 5번을 반복하면 끝

솔직히 그냥 배열 다루는 문젠데 내가 너무 복잡하게 생각했던 것 같다..ㅠ

근데 여전히 왜 lock을 lock.length + key.length * 2 만큼 새로 확장해야하는지 모르겠다..!!

내가 생각한 확장 범위는 lock.length + key.length * 2 - 2였다. 이렇게 하면 항상 한 지점은 걸치게 둘 수 있었기 때문이다.

배열 인덱스를 정하는 부분은 링크 에서 도움을 얻었다.

코드

class Solution {
    public int[][] rotate(int[][] key) {
        int[][] resultArr = new int[key.length][key.length];
        for (int i = 0; i < resultArr.length; i++) {
            int tempIdx = resultArr.length - 1;
            for (int j = 0; j < resultArr.length; j++) {
                resultArr[i][j] = key[tempIdx--][i];
            }
        }
        return resultArr;
    }
    public boolean locking(int[][] key, int[][] ag_lock, int x, int y) {
        for(int i = x; i < key.length + x; i++)
            for(int j = y; j < key.length + y; j++)
                ag_lock[i][j] += key[i - x][j - y];
        for(int i = key.length - 1; i < ag_lock.length - (key.length + 1); i++) {
            for(int j = key.length - 1; j < ag_lock.length - (key.length + 1); j++) {
                if(ag_lock[i][j] != 1){
                    for(int a = x; a < key.length + x; a++)
                        for(int b = y; b < key.length + y; b++)
                            ag_lock[a][b] -= key[a - x][b - y];                    
                    return false;
                }
            }
        }
        return true;
    }
    public boolean solution(int[][] key, int[][] lock) {
        int[][] ag_lock = new int[lock.length + key.length * 2 - 2][lock.length + key.length * 2 - 2];
        for(int i = 0; i < lock.length ; i++)
            for(int j = 0; j < lock.length; j++)
                ag_lock[i + key.length - 1][j + key.length - 1] = lock[i][j];
        for(int a = 1; a <= 4; a++) {
            for(int i = 0; i < ag_lock.length - (key.length + 1); i++) {
                for(int j = 0; j < ag_lock.length - (key.length + 1); j++) {
                    if(locking(key,ag_lock,i,j))
                        return true;
                }
            }
            key = rotate(key);
        }
        return false;
    }
}