입력값이 작아서 완전탐색이 가능하다고 판단했다.
회전 함수와 이동 함수를 각각 구현해 배열을 하나하나 대조해보는 수밖에 없다고 생각했다.
그래서 회전 함수와 이동 함수를 구현했다.
그리고 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
2차원 배열을 90도로 회전하는 기능을 transpose 함수로 구현한다.
len-1 - j
로 치환해주면 된다. isAnswer 함수를 통해 자물쇠와 열쇠가 맞는지 판단한다.
메인 로직은 다음과 같다.
로직을 이해하기 위한 그림을 아래와 같다.
그림 출처 : 프로그래머스 - 자물쇠와 열쇠
위와 같은 로직을 거치되, 배열을 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
}
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
}
[y] 자체는 가로줄(row)라고 볼 수 있지만,
[y][x]는 세로줄(column)이 아니라 하나의 좌표로 보는 게 좋다.
그러므로 좌표로 표현한다면,
col 또는 row 보다는 [y][x]라고 표현하는 게 깔끔해 보인다.
프로그래머스 - 자물쇠와 열쇠
[카카오기출/프로그래머스] 43.자물쇠와 열쇠
[프로그래머스/Javascript] 자물쇠와 열쇠