[프로그래머스 lev3/JS] 자물쇠와 열쇠

문제 출처

프로그래머스 lev3 - 자물쇠와 열쇠

나의 풀이 (실패)

입력값이 작아서 완전탐색이 가능하다고 판단했다.
회전 함수와 이동 함수를 각각 구현해 배열을 하나하나 대조해보는 수밖에 없다고 생각했다.

그래서 회전 함수와 이동 함수를 구현했다.
그리고 dfs를 통해 정답을 찾으려 했으나 RangeError: Maximum call stack size exceeded 에러가 발생했다. 이동함수를 따로 구현해서 재귀를 반복하기 보다는, 반복문으로 완전탐색을 진행했어야 했나보다..

// 삽질 코드
function rotateSquare(square, dir){
  let len = square.length
  let maxIdx = len - 1 
  let newSquare = Array.from({length: len}, () => new Array(len).fill(0))
  
  for(let i=0; i<square.length; i++){
    for(let j=0; j<square[i].length; j++){
      // 시계 방향 (default)
      let afterY = j 
      let afterX = maxIdx - i 

      // 반시계 방향
      if(dir === -1){
        afterY = maxIdx - j 
        afterX = i 
      }

      newSquare[afterY][afterX] = square[i][j]
    }
  }
  return newSquare
}

function moveSquare(square, dir) {
  let len = square.length
  let newSquare = Array.from({length: len}, () => new Array(len).fill(false))

  if(dir === 'right'){
    for(let i=0; i<square.length; i++){
      for(let j=0; j<square[i].length-1; j++){
  
        let afterY = i
        let afterX = j+1
        
        newSquare[afterY][afterX] = square[i][j]
      }
    }
  }
  else if(dir === 'left'){
    for(let i=0; i<square.length; i++){
      for(let j=1; j<square[i].length; j++){
  
        let afterY = i
        let afterX = j-1
        
        newSquare[afterY][afterX] = square[i][j]
      }
    }
  }
  else if(dir === 'bottom'){
    for(let i=0; i<square.length-1; i++){
      for(let j=0; j<square[i].length; j++){
  
        let afterY = i+1
        let afterX = j
        
        newSquare[afterY][afterX] = square[i][j]
      }
    }
  }
  else if(dir === 'top'){
    for(let i=1; i<square.length; i++){
      for(let j=0; j<square[i].length; j++){
  
        let afterY = i-1
        let afterX = j
        
        newSquare[afterY][afterX] = square[i][j]
      }
    }
  }
  return newSquare
}

function checkArr(arr1, arr2){
  for(let i=0; i<arr1.length; i++){
    for(let j=0; j<arr1[i].length; j++){
      if(arr1[i][j] !== arr2[i][j]) return false 
    }
  }
  return true 
}
function end(arr){
  for(let i=0; i<arr.length; i++){
    for(let j=0; j<arr[i].length; j++){
      if(arr[i][j] !== false) return false 
    }
  }
  return true 
}

function solution(key, lock) {
  let dir = ['top', 'right', 'bottom', 'left']
  let newKey = [...key]

  for(let i=0; i<4; i++){
    newKey = rotateSquare(newKey)
    if(checkArr(newKey, lock)) return true 
    else {
      let origin = [...newKey]
      if(dfs(origin)) return true 
    }
  }

  function dfs(arr){
    if(end(arr)) return false 

    for(let i=0; i<dir.length; i++){
      let newArr = moveSquare(arr, dir[i])
      if(checkArr(newArr, lock)) return true 
      else dfs(newArr)
    }
  }
}

console.log(
  solution(
    [
      [0, 0, 0],
      [1, 0, 0],
      [0, 1, 1],
    ],
    [
      [1, 1, 1],
      [1, 1, 0],
      [1, 0, 1],
    ]
  )
); // true 

다른 풀이 1

2차원 배열을 90도로 회전하는 기능을 transpose 함수로 구현한다.

• 2차원 배열을 90도로 회전하려면 => i와 j를 변경하고, j를 len-1 - j로 치환해주면 된다.

isAnswer 함수를 통해 자물쇠와 열쇠가 맞는지 판단한다.

• 판단 로직은 간단하게 구현하는데, 단순하게 newLock[i][j]가 전부 1이면 true이고 아니라면 false로 잡는다.

메인 로직은 다음과 같다.

• lock 배열을 고정시킨 뒤, key 배열을 회전시키거나 움직여가면서 하나씩 맞춰보면 되는데, 음수값을 제거하기 위해 lock 배열의 가로,세로 길이를 3배 늘린다. 그리고 기존의 lock 배열을 가운데에 위치시킨다.
• 90도 회전의 경우 4번만 하면 되기 때문에 i index로 transpose 함수를 실행한다.
• 각 회전에 대해서 3중 for문을 도는데,
• jMax와 kMax는 lock 배열의 우측하단 지점을 가리킨다.
• m과 n은 key 배열의 좌측상단 지점을 가리킨다.
• 열쇠가 맞지 않는 부분은 9999로 처리해주고, 맞는 부분은 1로 처리해서 정답을 판단할 수 있게 값을 설정해준다.

로직을 이해하기 위한 그림을 아래와 같다.
그림 출처 : 프로그래머스 - 자물쇠와 열쇠

위와 같은 로직을 거치되, 배열을 3배로 늘려서 겹치는 부분을 판단하는 원리이다.
그림 출처 : [카카오기출/프로그래머스] 43.자물쇠와 열쇠

const transpose = (key) => {
  const len = key.length
  const ret = Array.from(Array(len), () => Array(len))

  for (let i=0; i<len; ++i) {
    for (let j=0; j<len; ++j) {
      ret[i][j] = key[len - 1 - j][i]
    }
  }
  return ret
}

const isAnswer = (newLock, len) => {

  for (let i=len; i < len*2; i++) {
    for (let j=len; j < len*2; j++) {
      if (newLock[i][j] !== 1) return false
    }
  }
  return true
}

const solution = (key, lock) => {

  const len = lock.length
  const arr = Array.from(Array(len * 3), () => Array(len * 3))

  for (let i=len; i < len*2; i++) {
    for (let j=len; j < len*2; j++) {
      arr[i][j] = lock[i - len][j - len]
    }
  }
  // console.log(arr)

  for (let i=0; i<4; i++) {
    key = transpose(key)
    const keyLen = key.length 
    const jMax = arr.length - key.length
    const kMax = arr[0].length - key[0].length 

    for (let j=0; j<=jMax; j++) {
      for (let k=0; k<=kMax; k++) {
        const newLock = arr.map(el => el.slice()) 

        for (let m=0; m<keyLen; m++) {
          for (let n=0; n<keyLen; n++) {

            if (newLock[j + m][k + n]==1 && key[m][n]==1) {
              newLock[j + m][k + n] = 9999
            } 
            else if (newLock[j + m][k + n]==1 && key[m][n]==0) {
              newLock[j + m][k + n] = 1
            } 
            else newLock[j + m][k + n] = key[m][n]
          }
        }
        if (isAnswer(newLock, len)) return true
      }
    }
  }
  return false
}

2차원 배열 회전 (map 메서드, 2중 for)

const rotate = (matrix) => {
  return matrix[0].map((_,i) => matrix.map(r => r[i]).reverse())
}

풀어서 해석하면 이렇다.
2차원 배열 matrix[0]의 인덱스만 빌려와서
matrix.map에 가져온 인덱스를 사용한 뒤에 reverse() 메서드로 뒤집어서 return한다.

const rotate = (matrix) => {
  return matrix[0].map((_,i) => {
    console.log(i)

    return matrix.map(r => {
      console.log(r, r[i])
      return r[i]
    }).reverse()
  })
}

단순히 2중 for문을 사용하면 다음과 같다.
i와 j를 변경해주고, key.length-1에서 j를 빼준 값을 j로 치환해주면 90도로 회전한다.

const transpose = (key) => {
  const len = key.length
  const ret = Array.from(Array(len), () => Array(len))

  for (let i=0; i<len; ++i) {
    for (let j=0; j<len; ++j) {
      ret[i][j] = key[len - 1 - j][i]
    }
  }
  return ret
}

"[col][row] vs [y][x]" 혼동했던 것들 정리

[y] 자체는 가로줄(row)라고 볼 수 있지만, 
[y][x]는 세로줄(column)이 아니라 하나의 좌표로 보는 게 좋다.

그러므로 좌표로 표현한다면, 
col 또는 row 보다는 [y][x]라고 표현하는 게 깔끔해 보인다.

참고

프로그래머스 - 자물쇠와 열쇠
[카카오기출/프로그래머스] 43.자물쇠와 열쇠
[프로그래머스/Javascript] 자물쇠와 열쇠