[프로그래머스-60059]자물쇠와 열쇠

[시뮬레이션]-자물쇠와 열쇠

프로그래머스

문제 설명

NxN 크기의 정사각 격자의 형태인 자물쇠와 MxM 크기인 정사각 격자 형태의 열쇠가 존재하며, 자물쇠와 열쇠에는 홈과 돌기 부분이 존재한다.

열쇠는 회전과 이동이 가능하며, 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열린다.

• 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는데 영향을 주지 않는다.
• 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 한다. 또한 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안된다.
• 자물쇠의 모든 홈을 채워 비워있는 곳이 없어야 자물쇠를 열 수 있다.

제한사항

• 3 <= M <= 20
• 3 <= N <= 20
• 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

 

풀이 방법

Lock의 첫 번째 홈 부분을 찾아 Key의 돌기 부분을 끼워보며 조건에 만족하는지 확인하는 방법으로 접근함

1. Lock의 홈 부분(0) 찾아 배열 생성
2. Key의 돌기 부분(1) 찾아 배열 생성
3. Key의 돌기 위치들을 순회하면서 Lock의 첫 번째 홈 부분에 맞추기
4. Key 돌기 위치들을 Lock의 첫 번째 홈 부분에 맞게 위치 수정하기
5. 위치 변경 후 Key 돌기 위치들이 조건에 위배되는지 확인
   • 위치가 자물쇠의 영역을 벗어나는 경우 → 자물쇠 여는데 영향 X(무시)
   • key의 위치가 자물쇠의 돌기(1) 부분인 경우 → 지금까지 조건에 만족하는거 무효화시키기(회전시키기)
   • key의 위치가 자물쇠의 홈(0) 부분인 경우 → 조건에 만족하는 자물쇠의 홈 부분 카운트 증가
6. 자물쇠의 모든 홈을 다 채운 경우 바로 true 리턴
7. 충돌하거나 자물쇠의 모든 홈을 채우지 못한 경우 90도 회전 수행

그림 예시

회전 함수

• 기존 Key 배열을 다 회전시키지 않고, Key의 돌기 부분에 해당하는 위치만 회전시키기
• 90도 회전: [행, 열] → [열, 배열크기-1-행]

놓친 부분...

• 조건문으로 예외처리 해줘야함..
• 자물쇠 홈 부분 > 열쇠 돌기 개수 → 모든 홈을 채우지 못함 ► 바로 false 리턴
• 자물쇠가 모두 돌기인 경우, 즉 자물쇠 홈 부분=0 → 모든 홈이 다 채워짐 ► 바로 true 리턴

코드

function solution(key, lock) {
    const m = key.length; // 열쇠 크기
    const n = lock.length; // 자물쇠 크기
    
    const lockHome = []; // 자물쇠의 처음으로 나오는 홈 위치 찾기
    for(let r=0; r<n; r++) {
        for(let c=0; c<n; c++) {
            if(lock[r][c] === 0) lockHome.push([r, c]);
        }
    }
    
    const keyNotHome = []; // 열쇠의 돌기 위치 확인
    for(let r=0; r<m; r++) {
        for(let c=0; c<m; c++) {
            if(key[r][c] === 1) keyNotHome.push([r, c]);
        }
    }
    
    if(lockHome.length > keyNotHome.length) return false; // 자물쇠 홈 개수 > 열쇠 돌기 개수 -> 열 수 없음
    else if(lockHome.length === 0) return true; // 무조건 열 수 있음
    
    for(let k=0; k<keyNotHome.length; k++) {
        let origin = [...keyNotHome];
        // 0도, 90도, 180도, 270도
        for(let i=0; i<4; i++) {
            // 자물쇠의 첫 번째 홈이랑 열쇠 돌기랑 위치 맞추기
            const moveR = lockHome[0][0]-origin[k][0];
            const moveC = lockHome[0][1]-origin[k][1]; 
            const posKey = origin.map((pos) => [pos[0]+moveR, pos[1]+moveC]);

            let find = 0;
            for(const [pr, pc] of posKey) {
                if(pr < 0 || pr >= n || pc <0 || pc >= n) continue; // 범위 벗어나는건 무시
                // 자물쇠랑 열쇠가 충돌하는 경우 다음 회전 수행
                if(lock[pr][pc] === 1) {
                    find = 0;
                    break;
                } else {
                    find++;
                }
            }
            if(find === lockHome.length) return true; // 자물쇠의 모든 홈과 맞을 경우
            else {
                origin = rotate(origin, m);
            }
        }
    } 
    return false;
    
}
// 회전
function rotate(key, m) {
    // 1행 -> 3열, 2행 -> 2열, 3행 -> 1열
    const rotateKey = [];
    for(const [r, c] of key) {
        rotateKey.push([c, m-1-r]);
    }
    return rotateKey;
}