Programmers / Level 3 / 자물쇠와 열쇠 / JS

문제 설명

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 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 verification(key, r, c, lock) {
    // 깊은 복사
    let lock_copy = JSON.parse(JSON.stringify(lock));
    const len = lock_copy.length;
    
    // 키의 돌기부분 보다 자물쇠의 홈 부분이 더 많을 경우
    const key_teeth = key.flat().filter(el => el === 1).length; // 키의 돌기부분의 갯수
    let lock_notch = lock.flat().filter(el => el === 0).length; // 자물쇠의 홈의 갯수
    
    if(key_teeth < lock_notch) return false;
    
    for(let i=0; i<key.length; i++) {
        for(let j=0; j<key.length; j++) {
            // 범위 체크, 자물쇠의 범위를 벗어난것은 영향을 주지않음
            if((i+r >= len) || (j+c >= len) || (i+r < 0) || (j+c < 0)) continue;
            // 열쇠가 이동한 위치에 자물쇠가 막혀있을 경우
            if(lock_copy[i+r][j+c] && key[i][j]) return false;
            // 열쇠가 이동한 위치가 자물쇠의 홈 부분일 경우
            // 1로 채워줌
            if(!lock_copy[i+r][j+c] && key[i][j]) lock_copy[i+r][j+c] = 1;
        }
    }
    
    // 자물쇠에 홈이 채워지지 않은 경우 false
    lock_notch = lock_copy.flat().filter(el => el === 0).length; // 자물쇠의 홈의 갯수
    if(lock_notch > 0) return false;
    
    return true;
}

// 오른쪽으로 90도 회전
function rotate(key) {
    // 깊은 복사
    let key_copy = JSON.parse(JSON.stringify(key));
    
    for(let i=0; i<key.length; i++) {
        for(let j=0; j<key.length; j++) {
            key[i][j] = key_copy[key.length-j-1][i];
        }
    }
}

function solution(key, lock) {
    let result = false;
    
    for(let rotate_cnt=1; rotate_cnt<=4; rotate_cnt++) {
        rotate(key);
        
        for(let i=(-lock.length); i<lock.length; i++) {
            for(let j=(-lock.length); j<lock.length; j++) {
                result = result || verification(key, i, j, lock);
            }
        }
    }
    
    return result;
}

---

90도씩 돌리고, 한칸씩 옮겨가면서 검사했다.

처음부터 생각한 로직대로 짰는데, 복사와 인덱스부분에서 해메서 다른 분들의 아이디어를 참고해보았다.

 

제일 처음 겪었던 것은 함수에 배열을 인자로 전달할때였다.

인수로 전달할시에 얕은복사가 이루어져서 회전이나 이동시에 제대로 되지 않았다.

따라서 깊은 복사 방법인 JSON.parse(JSON.stringify(arr))를 사용하였다.

 

두번째로는 배열의 인덱스 문제였다.

문제에서 볼 수 있듯이 범위를 벗어난 열쇠는 자물쇠와 매칭시킬때 무시된다.

따라서 범위를 늘려주어서 padding을 넣어주거나, 무시를 해주어야 하는데 체크를 제대로 안해주어서 계속 틀렸다.

 

회전과 이동의 구현은 쉬웠지만 인덱스를 생각하면서 조건을 달아주는 것이 까다로운 문제라고 생각한다.