[JS] 자물쇠와 열쇠 - 디버깅 지옥 멈춰! true/false 멈춰!

Boolean 폭력 멈춰!!

 

이 문제 진짜 개애애빡치는게 뭐 결과가 true/false 두 개여가지고

어디서 문제 있는건지 알 수도 없고.. 결국엔 질문 게시판에 계신 현자분의 아이디어를 쓱싹해서 완성했네용진짜 지옥의 백트래킹입니다.같이 한 번 볼까요?

---

문제 요약

 

진짜 저 튜브 저쉑 "이거도 못푸는 거야?" 이러는거 같아서 3일동안 풀었어용

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

 

제한사항

• 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은 돌기 부분을 나타냅니다.

 

테스트케이스

testcase	lock	return
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

 

접근 방법

일단 수많은 트라이를 해봤는데요.. (진짜 많이함 한 20번 넘게)

과정을 정리해보면 이렇습니다.

 

1. key(M x M 2중 배열)를 90도 회전시킬줄 알아야합니다.
(제가 어제 정리한 글을 참고하면 조금 도움이 될 듯 합니다.)

2022.08.09 - [알고리즘] - 배열을 90도 회전시키는 방법

배열을 90도 회전시키는 방법

 

2. 4중 루프의 탐색이 필요합니다.
- lock의 탐색 시작점을 나타내는 루프 2개, 그리고 key의 row, col을 나타내는 루프 2개입니다.
- 문제에도 적혀있지만, key를 회전한 다음 오른쪽으로 한 칸, 아래로 한 칸을 내려야합니다.
- 이런 비교를 위해서는 key는 항상 [0][0]부터 비교를 시작하고 lock의 시작 위치를 계속 변경해줘야합니다.

 

루프를 돌리는데에 정말 다양한 방식을 시도해봤었습니다.

- lock의 돌기부분(1)을 다 제거하고 key에 [0][0] 부터 [N][N]까지 넣어보기.

- key의 홈부분(0)을 제거하고 lock의 [0][0]부터 [M][M]까지 다 넣어보기.

 

그 안에서도 뭐 어떤 조건일때 continue, break 바깥 순회에서도 boolean 변수 만들어서 break 뭐 많이 해봤습니다.

근데 핵심은 이런게 아니었고 다른데 있었습니다.

 

https://school.programmers.co.kr/questions/20370

프로그래머스

 

저는 계속 key의 [0][0] 기준으로 lock과 비교했었는데 생각해보니 key의 [M][M]부분이 lock의 [0][0]과 겹칠 수 있더군요.

그러니 lock의 시작점을 정해주는 loop를 음수(-N)부터 돌려줘야합니다.

 

정답 코드

function rotate(arr) {
    const [maxRow, maxCol] = [arr.length, arr[0].length];
    const result = Array.from({length: maxCol}, () => Array(maxRow).fill(0));
    for (let row = 0; row < maxRow; row++) {
        for (let col = 0; col < maxCol; col++) {
            result[col][maxRow - row - 1] = arr[row][col];
        }
    }
    return result;
}

function solution(key, lock) {
    const N = lock.length;
    const M = key.length;
    let currKey = key.map(v => [...v]);
    let currLock = lock.map(v => [...v]);
    let turn = 0;
    while (turn < 4) {
        for (let i = -N; i < N; i++) {
            for (let j = -N; j < N; j++) {
                for (let row = 0; row < M; row++) {
                    if (i + row < 0) continue;
                    for (let col = 0; col < M; col++) {
                        if (j + col < 0) continue;
                        if (col + j >= N || row + i >= N) break;
                        if (currLock[i + row][j + col] === 1 && currKey[row][col] === 1) break;
                        if (currLock[i + row][j + col] === 0 && currKey[row][col] === 1) {
                            currLock[i + row][j + col] = 1;
                        }
                    }
                }
                if (currLock.flatMap(v => v).every(v => v === 1)) return true;
                currLock = lock.map(v => [...v]);
            }
        }
        currKey = rotate(currKey);
        turn++;
    }
    
    return false;
}

 

팁 1. 다차원 배열의 초기화 방법

let currKey = key.map(v => [...v]);
let currLock = lock.map(v => [...v]);

 

js에서 다차원 배열을 그냥 넣게 되면 그건 얕은 복사로 처리됩니다.

// let currKey = key; (x)
// let currLock = lock; (x)

이렇게 넣게 되면 만약 currKey의 index로 접근해서 값을 바꿔준다면 원본인 key 역시 바뀌게 됩니다.

그렇기 때문에 꼭 map과 spread 연산자를 이용해서 원시수준 자료형태까지 접근해서 갱신해주도록 합시다!

 

팁 2. turn은 뭔가요?

90도 회전을 4번하는 순간부터는 원래 최초의 배열로 돌아오기 때문에 더 이상 조사할 필요가 없습니다.바로 false를 return 하면 되는거죠

 

팁 3. continue와 break 분기 설명좀 해주세요

for (let i = -N; i < N; i++) {
	// i는 lock을 탐색할 때 시작할 row입니다.
    for (let j = -N; j < N; j++) {
    	// j는 lock을 탐색할 때 시작할 col입니다.
        for (let row = 0; row < M; row++) {
        	// i + row는 key[row]와 비교할 lock의 row입니다.
            if (i + row < 0) continue;
            for (let col = 0; col < M; col++) {
            	// j + col은 key[col]과 비교할 lock의 col입니다.
                if (j + col < 0) continue;
                // lock의 테두리인 N까지 범위한정.
                if (col + j >= N || row + i >= N) break;
                // 같은 돌기 부분이라면 키는 맞지 않습니다.
                if (currLock[i + row][j + col] === 1 && currKey[row][col] === 1) break;
                if (currLock[i + row][j + col] === 0 && currKey[row][col] === 1) {
                    currLock[i + row][j + col] = 1;
                }
            }
        }
        if (currLock.flatMap(v => v).every(v => v === 1)) return true;
        currLock = lock.map(v => [...v]);
    }
}

 

주석을 한 번 달아봤습니다. 각 루프가 뭘 의미하는지 좀 이해가 쉬울 것 같습니다...만 continue와 break를 구분하는 이유를 좀 더 설명해야할 것 같습니다.

 

먼저 i + row로 우리는 currLock에 접근할 겁니다.

js에서 음수 index는 지원하지 않기 때문에 음수가 나온다면 continue를 합니다.

(왜 break가 아니냐면 key[3][3]과 lock[0][0] 같이 비교할 일이 있기 때문입니다. 이때 i는 -3, row는 3이 되겠네요. break 해주면 이런 케이스를 잡아낼 수가 없습니다.)

 

같은 맥락의 j + col입니다.

 

그리고 문제를 잘 읽어야한다는 점을 또 알려주는 같은 돌기 부분에서의 처리입니다.

과감히 break해서 처리하지 않고 다음 분기로 넘어갑시다!

 

정말 많은 케이스를 다뤄야하는 문제입니다.

이 문제의 진짜 악랄한 점은 결과가 boolean이라는 점입니다. 뭐 맞게 해서 true/ false가 나온건지 전혀 알길이 없어요.

실제로 아무것도 안하고 return true 해도 그냥 60점 정도 나오더라구요.

암튼.. 정말 스트레스 많은 3일이었네요.

그래도 이문제는 졸업했습니다!!!!

그럼 이만!