🔐[프로그래머스] 자물쇠와 열쇠

해당 게시물은 답수님의 tistory 블로그를 참고하여 작성되었음을 미리 밝힙니다.

😣문제 설명

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

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

---

🤔입출력 예

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

😮입출력 예에 대한 설명

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

🦍나의 풀이

function solution(key,lock) {
    // key값을 입력받아 모든 경우의 수를 조회할 수 있는 정사각형 생성
    const [keyLen, lockLen] = [key.length, lock.length];
    const totalLen = lockLen + keyLen*2 - 2;
    // board 배열 생성
    const board = Array(totalLen).fill().map(_ => Array(totalLen).fill());

    // board 정중앙에 락 배열 값 삽입
    for (let i = keyLen-1; i < keyLen + lockLen - 1; i++) {
        for (let j = keyLen-1; j < keyLen + lockLen - 1; j++) {
            board[i][j] = lock[i-(keyLen-1)][j-(keyLen-1)];
        }
    }
    // 정사각형 배열을 크기에 상관없이 회전시킴
    const rotateRight = (arr) => {
        const len = arr.length;
        // 정사각형 배열 생성
        const tmp = Array(len).fill().map(_ => Array(len).fill());
        // 회전
        for (let i = 0; i < len; i++) {
            for (let j = 0; j < len; j++) {
                tmp[j][len-1-i] = key[i][j];
            }
        }
        return tmp;
    };
    // 자물쇠가 열리는지 검사
    const isValid = (arr) => {
        // board 배열에서 실제 락 배열의 값이 포함된 부분만 검사한다.
        for (let i = keyLen-1; i < keyLen + lockLen -1; i++) {
            for (let j = keyLen-1; j < keyLen + lockLen -1; j++) {
                if (arr[i][j] !== 1) return false;
            }
        }
        return true;
    };
    // 키를 돌려가며 모든 경우의 수 탐색
    for (let rotate = 0; rotate < 4; rotate++) {
        // 작업 수행 최소화 위해 처음에는 로테이션 안 함
        key = rotate === 0 ? key : rotateRight(key);
        for (let i = 0; i <= totalLen - keyLen; i++) {
            for (let j = 0; j <= totalLen - keyLen; j++) {
                // 전개 연산자를 통해 board 원본 값에 영향주지 않도록 카피
                const boardCopy = board.map(arr => [...arr]);
                for (let r = 0; r < keyLen; r++) {
                    for (let c = 0; c < keyLen; c++) {
                        // 열쇠의 홈과 자물쇠의 홈이 만나면 안 되기 때문에 홈끼리 만나는 경우 값 2로 수정
                        if (key[r][c] === 1 && boardCopy[i+r][j+c] === 1) boardCopy[i+r][j+c] = 2;
                        else if (key[r][c] === 1 && boardCopy[i+r][j+c] === 0) boardCopy[i+r][j+c] = 1;
                    }
                }
                if (isValid(boardCopy) === true) return true;
            }
        }
    }
    return false
}

해당 문제의 중요 포인트는 원래 자물쇠 배열보다 큰 배열을 만들어 테스트 하는 것이다.

다른 포인트로는 키를 돌리는 방법이 너무 인상깊었는데

정사각형 기준 i와 j를 변의 길이만큼 반복하며,
길이에서 1을 뺀 값에 i를 추가로 빼주면 90도 회전을 구현할 수 있는 것 같음

// 회전
        for (let i = 0; i < len; i++) {
            for (let j = 0; j < len; j++) {
                tmp[j][len-1-i] = key[i][j];
            }
        }