2020 KAKAO CODING TEST (3) : 자물쇠와 열쇠

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

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

문제 설명

---

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

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

 

입출력

---

key	lock	result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

 

접근 방법

---

더 좋은 방법이 있을지 모르지만 저는 단순하게 (0,0)부터 KEY를 대입하여 맞는지 판단하고 안되면 90도 회전후 

동일한 방식을 반복했습니다. 다른 분의 풀이를 보고 더 좋은 방법이 있으면 추가해보겠습니다.~

 

(1). Lock 배열의 가로, 세로 3배의 background 배열을 생성, 중간에 Lock 배열값을 넣어준다.

(3배로 하는 이유는 위, 아래, 중앙 그리고 왼쪽, 오른쪽, 중앙이기 때문에 가로 세로에 3배를 해주는 것입니다.)

 

 (2). background에 0, 0 부터 key배열을 더해준다.

 

(3). background에 Lock영역에서 홈과 돌기가 모두 맞는지 확인. 모든값이 1이어야 함 (겹치는 부분은 2, 홈이면 0)

 

(3-1). 홈과 돌기가 맞지 않는 경우 key의 좌표를 한칸씩 이동하면서 (2)번 반복

 

(3-2). 모든 좌표를 반복하여 확인했을 때도 맞지 않는경우, Key 배열을 90도 돌리고 (2)번 반복

 

 

코드

---

[Python Solution]

def rotate_key(_key):
    key_size = len(_key)
    temp_key = [[0] * key_size for i in range(0, key_size)]
    reverse_i = key_size - 1
    for i in range(key_size):
        for j in range(key_size):
            temp_key [j] [reverse_i] = _key [i] [j]
        reverse_i -= 1

    return temp_key


def is_unlock(bg_size, _lock, _key, start_x, start_y, c_start, c_end):
    bg = [[0] * bg_size for i in range(0, bg_size)]

    # 1. put key in background
    for i in range(0, len(_key)):
        for j in range(0, len(_key)):
            bg [start_y + i] [start_x + j] += _key [i] [j]

    # 2. put lock in background
    for i in range(c_start, c_end):
        for j in range(c_start, c_end):
            bg [i] [j] += _lock [i - c_start] [j - c_start]
            # lock + key == 1이 안닌 경우 False
            if bg [i] [j] != 1:
                return False

    return True


def unlock(_lock, _key):
    lock_size = len(_lock)
    c_start = len(_key) - 1  # center 좌표
    c_end = c_start + lock_size
    bg_size = lock_size + (2 * c_start)  # 처음부터 1개 겹쳐서 비교하기 위해

    for x in range(0, 4):
        for i in range(0, c_end):
            for j in range(0, c_end):
                if is_unlock(bg_size, _lock, _key, i, j, c_start, c_end) is True:
                    return True
        # key를 90도 돌린다.
        _key = rotate_key(_key)

    return False


if __name__ == "__main__":
    lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
    key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
    print(unlock(lock, key))

[C++ Solution]

#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = true;
    bool chk2,chk0;
    int key_size=key.size();
    int lock_size=lock.size();
    
    int garo= (key_size-1)*2 + lock_size;
    
    //전체 백터에 lock을 넣는다
    vector<vector<int> >vec(garo, vector<int>(garo,0));
    for(int i=key_size-1;i<(key_size-1)+lock_size;i++){
        for(int j=key_size-1;j<(key_size-1)+lock_size;j++){
            vec[i][j]=lock[i-(key_size-1)][j-(key_size-1)];
        }
    }
    int rotate_chk=0;
    while(true){
        //회전을 모두 끝낸경우 
        if(rotate_chk==4)break;
        //전체백터를 카피할 새로운 백터
        vector<vector<int> >temp(garo, vector<int>(garo,0));
        
        for(int i=0;i<garo-(key_size-1);i++){
            for(int j=0;j<garo-(key_size-1);j++){
                fill(temp.begin(),temp.end(),vector<int>(garo,0));
                temp=vec;
                //vec & key >> all 1 >> 2,0 있으면 탈락
                bool chk2=false;
                for(int k=0;k<key_size;k++){
                    for(int l=0;l<key_size;l++){
                        temp[i+k][j+l]+=key[k][l];
                        if(temp[i+k][j+l]==2){chk2=true;break;}
                    }
                    if(chk2==true)break;
                }
              
                if(chk2==true)continue;
                else{
                    chk0=false;
                    //내부 lock에 맞는지 확인
                    for(int i=key_size-1;i<(key_size-1)+lock_size;i++){
                        for(int j=key_size-1;j<(key_size-1)+lock_size;j++){
                            if(temp[i][j]==0){chk0=true;break;}
                        }
                        if(chk0==true)break;
                    }
                }
                if(chk0==true){continue;}
                else if(chk0==false) break;
            }
            if(chk0==false){vec=temp;break;}
        }
        
        if(chk0==false)break;
        //위로가서 회전진행
        vector<vector<int>> temp_key(key_size,vector<int>(key_size,0));
        temp_key=key;
        for(int i=0;i<key_size;i++){
            for(int j=0;j<key_size;j++){
                temp_key[i][j]=key[j][key_size-i-1];
            }
        }
        key=temp_key;
        rotate_chk++;
    }
    if(chk0==false)answer = true;
    else answer=false;
    
    return answer;
}

funny algorithms~ :)