[프로그래머스] LV.3 자물쇠와 열쇠 (JS)

KG·2021년 4월 22일
Lv.3알고리즘완전탐색카카오프로그래머스
1

알고리즘

목록 보기
31/61
post-thumbnail

문제

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

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

입출력 예시

keylockresult
[[0, 0, 0], [1, 0, 0], [0, 1, 1]][[1, 1, 1], [1, 1, 0], [1, 0, 1]]true

풀이

2020 카카오 블라인드 테스트에서 출제된 문제이다. 종종 2차원 배열을 극한으로 다루는 문제가 출제되는 것 같다. 해당 문제 역시 특별한 알고리즘 기술이나 효율성을 요구하기 보다는 완전탐색으로 주어진 조건에 맞게 배열을 샅샅히 탐색하는지 요구하는 문제에 가깝다. 즉 구현력을 좀 더 보는 문제이다.

주어지는 M과 N 값이 매우 작고, 효율성을 따로 체크하는 문제도 아니기 때문에 효율성과 관련된 부분은 크게 신경쓰지 않고 작성하다보니 for문이 5번이나 중첩되는데도 정상적으로 통과가 되었다.

해당 문제를 푸는 방법 자체는 그렇게 어렵지 않다. 주어진 key 배열을 이용하여 lock 배열의 빈 칸을 모두 채울 수 있는지 검사하면 된다. 이때 key 배열은 90도로 회전이 가능하고 key 의 돌기 부분(1)이 lock의 돌기 부분(1)과 겹치면 안 된다. 이 점을 주의해서 key 배열을 돌려가며 모든 경우를 하나하나 대입하며 잠금을 해제할 수 있는지 체크해주면 될 것 이다.

배열 확장

문제를 조금 더 편하게 접근하기 위해 한 가지 생각을 해 볼 수 있다. 모든 경우를 탐색해야 하기 때문에 주어진 key의 가장자리부터 하나씩 lock 배열에 대입하며 접근해야 할 것이다. 즉 첫 비교시에는 key 배열의 가장자리칸을 제외한 나머지 칸은 모두 lock 배열 외부에 위치하게 될 것이다. 그리고 이는 lock 배열 각 모서리에 모두 공통되는 사항이다. 이때 일일히 key 배열의 원소 하나만을 갖고 와서 대입할 수 있겠지만 약간 번거롭다. 따라서 우리는 lock 배열과 key 배열을 합친 만큼의 가로x세로 길이를 가진 배열을 하나 만들어서 탐색할 것 이다. 그림으로 나타내면 다음과 같다.

노란색 테두리가 key 배열이고 빨간색 테두리가 lock 배열이고 주황색 음영은 서로 겹친 부분이라고 하자. lock 배열의 모서리에 다음과 같이 key 배열의 탐색이 이루어질 것이기 때문에 다음과 같이 배열을 확장하여 탐색이 이루어질 공간을 만들어 줄 수 있다.

위 전체 배열에서 가운데 빨간 부분은 lock 배열의 값으로 고정시키고 key 값은 전체배열의 시작부분부터 마지막부분까지 이동하게 된다면 편하게 일치여부를 확인할 수 있을 것이다. 따라서 위의 전체 배열을 만들어주는 함수를 하나 작성해주자.

// arr 매개변수는 lock, len은 key 배열의 길이이다.
const makeBoard = (arr, len) => {
  // 두 배열의 크기차이를 구한다.
  // 2를 곱해주는 이유는 가로/세로 관점에서 최대 2개의
  // key 배열이 왼쪽-오른쪽/위쪽-아래쪽에 추가되기 때문
  const diff = (arr.length - len) * 2
  // 전체 배열의 크기를 구한다.
  // 전체 배열의 크기는 lock 배열 크기의 3배에서
  // 사이드에 추가되는 key 배열이 각각 모서리 1칸씩 점유하므로 2를 빼주고
  // 위에서 구한 diff 를 빼준 값이 된다.
  const blocks = arr.length * 3 - 2 - diff;
  
  // blocks 크기 만큼의 확장된 2차원 배열을 생성
  return new Array(blocks).fill().map((_, idx) => {
    // div 영역은 전체 배열에서 중앙에 위치하는 lock 배열의 공간이다.
    const div = (blocks - arr.length) / 2;
    // 해당 위치가 전체배열의 중앙이라면
    if(idx >= div && idx < div + arr.length) {
      // lock 배열을 초과하는 나머지 배열은 0으로 채우고
      const fb = new Array(div).fill(0);
      // 중앙 부분은 기존 lock 배열의 값을 넣어준다.
      return [...fb, ...arr[idx-div], ...fb];
    }
    // 해당 위치는 lock 배열 외부의 공간이므로
    // 모두 0으로 초기화한다.
    return new Array(blocks).fill(0);
  });
}

위 함수를 통해 우리는 위에 이미지에서 제시한 전체 탐색 배열을 하나 만들어 줄 수 있다.

key 배열 회전

문제 조건에 따라서 key 배열은 90도씩 회전할 수 있다. 따라서 90도씩 회전하는 함수를 하나 만들어주자. 2차원 배열의 회전은 2중 반복문을 만들어 i 와 j 값을 바꾸어주는 것으로 간단히 구현할 수 있다.

const rotate = (arr) => {
  // 배열을 리턴해줄 것이므로 map 함수를 사용하여 2중 반복 처리
  return arr.map((_, idx) => {
    const rest = [];
    // 배열의 마지막부터 접근하여
    // 마지막원소(i)와 현재위치(idx)를 교환해준다.
    for(let i = arr.length - 1; i >= 0; i--)
      rest.push(arr[i][idx]);
    return rest;
  });
}

잠금 해제 체크

다음은 반복문을 돌면서 입력되는 key으로 현재 자물쇠를 열 수 있는지 없는지를 체크해주는 함수를 만들어주자. key와 lock 배열 모두 돌기 부분은 1, 비어있는 공간은 0으로 선언되어 있다. 따라서 열 수 있는 조건은 lock 배열과 입력된 key 배열을 각자의 위치에서 모두 더했을 때 모든 값이 1이 되어야 한다.

매개변수로 전달받는 값은 총 3개 이다. 하나는 앞서 만들어준 전체 탐색 배열이고, 이때 key 배열과 lock 배열의 길이를 전달해주자. 두 배열의 길이를 통해 slice 함수를 사용해 가운데에 위치한 lock 배열의 공간을 탐색할 것이다.

// klen = key 배열의 길이, llen = lock 배열의 길이
const isCheck = (arr, klen, llen) => {
  // 전체 배열에서 가운데 위치한 자물쇠의 영역은
  // arr.slice(start, last)가 된다.
  const start = klen - 1;
  const last = start + llen;
  
  // outer는 전체 배열에서 lock 배열이 있는 첫 행
  for(const outer of arr.slice(start, last)) {
    // inner은 첫 행에서 lock 배열만의 행을 말한다.
    for(const inner of outer.slice(start, last)) {
      // 이 값이 1이 아니라는 것은 잠금해제가 불가한 것
      if(inner !== 1) return false;
    }
  }
  
  // 위 반복을 모두 통과하면 lock이 모두 1이 된 상태이므로
  // 잠금해제가 가능한 상태를 말한다.
  return true;
}

완전탐색

앞서서 우리는 완전탐색에 필요한 3가지 유틸성 함수를 모두 만들어주었다. 이제는 이 3가지 함수를 가지고 전체배열을 4번씩 탐색해 줄 것이다. 4번씩 탐색해주는 이유는 key 배열을 90도씩 총 4번 회전할 수 있기 때문이다.

먼저 반복문을 돌리기 전에 초기 상태를 정의해주자. 전체 탐색 배열을 하나 만들어두고, 현재 key 값과 동일한 배열을 하나 만들어주자. 이를 통해 우리는 key 배열을 4번씩 90도 회전을 하게 만들어 줄 것 이다.

const board = makeBoard(lock, key.length);
let copy_key = key;

다음은 반복문을 돌면서 90도씩 전환한 key 값을 가지고 전체 탐색 배열에 위치한 중앙 부분에 각각의 값을 더해줄 것이다. 이때 배열의 값을 수정하기 때문에 원본 배열의 값이 변하게 된다. 이를 방지하기 위해 원본 배열을 복사하여 그 값을 활용해야 하는데, 자바스크립트에서는 배열과 같은 참조값은 얕은 복사(Shallow Copy)가 일어난다. 따라서 slice 또는 전개연산자를 통한 기법을 이용해 원본 배열을 복사하더라도, 복사한 배열에서 값의 수정이 일어나면 원본 배열까지 그 변화가 적용된다.

따라서 이를 방지하기 위해서는 깊은 복사(Deep Copy)를 해야하는데, 우리 자바스크립트는 깊은 복사를 하는 것 마저 여간 까다로운 점이 한 두가지가 아니다. 재귀함수를 구현하여 가장 밑의 depth 까지 내려가 복사를 하는 것이 비교적 정석적인 방법으로 알려져 있으나, 코딩 테스트에서 이를 또 구현하는 것은 번거롭다. 다행히 코딩 테스트는 입력값의 형태가 고정되어 있기 때문에 다른 경우의 수는 고려해주지 않아도 된다. 따라서 우회적인 방법을 사용해 간단하게 깊은 복사를 수행하자. 이는 JSON.stringify() 함수를 통해 만들어 줄 수 있다. 해당 함수는 입력받은 값을 JSON 객체로 만들어주고 이를 다시 JSON.parse() 함수를 통해 번역하면 원본 객체와 참조가 끊긴 새로운 값을 만들 수 있다. 물론 이 역시 완벽한 깊은 복사 방법은 아닌데, 깊은 복사와 얕은 복사에 관한 이야기는 추후 포스팅을 하도록 하겠다. 어쨌든 우리는 해당 문제에서 JSON 함수를 가지고 참조값을 복사할 것이다.

// 총 4번 반복을 할 것이다. 4번 회전이 가능하기 때문이다.
for(let i = 0; i < 4; i++) {
  // 처음부터 회전을 적용하여 시작한다. 때문에 4번 반복을 하는 것이다.
  copy_key = rotate(copy_key);
  
  // 전체 탐색 배열에서 오직 key 배열만 처음부터 끝까지
  // 위치를 이동하며 탐색을 진행한다.
  // 이때 시작위치는 0이며, 종료위치는 마지막 원소에서
  // key 배열의 길이만틈 떨어진 곳이 될 것이다.
  for(let j = 0; j <= board.length - key.length; j++) {
    for(let k = 0; k <= board.length - key.length; k++) {
      // JSON 함수를 이용해 원본 전체 탐색 배열을 복사
      const copy_lock = JSON.parse(JSON.stringify(board));
      
      // key에 담긴 값(= copy_key[l][m])을
      // 현재 key가 위치하고 있는 전체 탐색 배열 위치
      // copy_lock[j+l][k+m]과 더해줄 것 이다.
      for(let l = 0; l < key.length; l++) {
        for(let m = 0; m < key.length; m++) {
          copy_lock[j+l][k+m] += copy_key[l][m];
        }
      }
      
      // 계산이 완료된 copy_lock을 체크함수에 전달
      answer = isCheck(copy_lock, key.length, lock.length);
      // 만일 잠금해제가 가능한 상태면 바로 반복을 종료하고 정답을 리턴
      if(answer) return answer;
    }
  }
}

// 위의 반복문이 도중에 종료되지 않았다면
// 잠금해제가 가능한 경우가 없었다는 것이므로 false 리턴
return false;

전체코드

주석을 제외한 전체 코드는 다음과 같다. 배열을 다루는 것이 까다로운 점을 제외하면 사실 난이도는 그렇게 높지 않지만, 구현력이 다소 많이 요구되는 문제인 것 같다. 효율성은 고민하지 않았기 때문에 다른 방식으로도 더 좋은 풀이가 많이 있을 것으로 생각된다.

function solution (key, lock) {
  let answer = false;
  
  const board = makeBoard(lock, key.length);
  let copy_key = key;
  
  for(let i = 0; i < 4; i++) {
    copy_key = rotate(copy_key);
    
    for(let j = 0; j <= board.length - key.length; j++) {
      for(let k = 0; k <= board.length - key.length; k++) {
        const copy_lock = JSON.parse(JSON.stringify(board));
        
        for(let l = 0; l < key.length; l++) {
          for(let m = 0; m < key.length; m++) {
            copy_lock[j+l][k+m] += copy_key[l][m];
          }
        }
        
        answer = isCheck(copy_lock, key.length, lock.length);
        if(answer) return answer;
      }
    }
  }
  
  return answer;
}

const rotate = (arr) => {
  return arr.map((_, idx) => {
    const rest = [];
    for(let i = arr.length - 1; i >= 0; i--)
      rest.push(arr[i][idx]);
    return rest;
  });
}

const makeBoard = (arr, len) => {
    const diff = (arr.length - len) * 2;
    const blocks = arr.length * 3 - 2 - diff;
    
    return new Array(blocks).fill().map((_, idx) => {
      const div = (blocks - arr.length) / 2;
      if(idx >= div && idx < div+arr.length) {
        const fb = new Array(div).fill(0);
        return [...fb, ...arr[idx-div], ...fb];
      }
      return new Array(blocks).fill(0);
    });
}

const isCheck = (arr, klen, llen) => {
  const start = klen - 1;
  const last = start + llen;
  
  for(const outer of arr.slice(start, last)) {
    for(const inner of outer.slice(start, last)) {
      if(inner !== 1) return false;
    }
  }
  
  return true;
}

출처

https://programmers.co.kr/learn/courses/30/lessons/60059#

profile
KG
개발잘하고싶다
이전 포스트

[프로그래머스] LV.3 추석 트래픽 (JS)

다음 포스트

[프로그래머스] LV.3 합승 택시 요금 (JS)

0개의 댓글