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

---

📌 문제 설명

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 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

 

🔗 문제 링크

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

프로그래머스

---

반응형

💡 풀이 아이디어

• 열쇠를 90도로 회전 + 이동
• 회전한 열쇠를 이동시키며 자물쇠와 비교하기

 

📝 최종 풀이

• 함수 설명
  • rotateKey는 key를 시계방향으로 90도 회전하여 반환하는 함수입니다.
  • moveKey는 확장된 lock의 시작점과 끝점까지 이동시키며 원래 lock과 겹치는 부분을 반환하는 함수입니다.
  • isUnlock은 key와 lock을 비교하여 열 수 있는지 여부를 확인하여 반환하는 함수입니다.
• 초기화
  • 기존의 lock을 key와 비교하기 용이하도록 확장시킵니다.
•  반복문
  • rotateKey 함수를 이용하여 0도, 90도, 180도, 270도 회전하는 4가지 경우를 비교합니다.
  • moveKey 함수를 이용하여 각 회전된 key를 원래 lock과 이동시키며 비교하여 반환합니다.
  • moveKey 함수에서 반환된 key와 기존의 lock을 isUnlock 함수에 사용해 열 수 있는 여부를 확인합니다.
• 정답
  • 반복문을 돌며 열 수 있는 경우가 있다면 true를 반환합니다.
  • 반복문이 종료된 후에도 열 수 없었다면 false를 반환합니다.

---

728x90

👩‍💻 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> rotateKey(const vector<vector<int>> &key){
    int m = key.size();
    vector<vector<int>> newKey(m, vector<int>(m, 0));
    
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            newKey[j][m-i-1] = key[i][j];
        }
    }
    
    return newKey;
}

vector<vector<int>> moveKey(const vector<vector<int>> lock, const vector<vector<int>> key, int dx, int dy, int N){
    int n = lock.size();
    int m = key.size();
    vector<vector<int>> tempLock(n, vector<int> (n, 0));
    vector<vector<int>> tempKey;
    
    for(int i=0; i<m; i++){
        for(int j=0; j<m; j++){
            int x = dx + i;
            int y = dy + j;
            
            tempLock[x][y] += key[i][j];
        }
    }
    
    for(int i=m-1; i<m-1+N; i++){
        vector<int> temp;
        for(int j=m-1; j<m-1+N; j++){
            temp.push_back(tempLock[i][j]);
        }
        tempKey.push_back(temp);
    }
    
    return tempKey;
}

bool isUnlock(const vector<vector<int>> &lock, const vector<vector<int>> &key){
    int n = lock.size();
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(lock[i][j] == key[i][j]){
                return false;
            }
        }
    }
    
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int n = lock.size();
    int m = key.size();
    int nn = n + 2 * (m - 1);
    
    vector<vector<int>> newLock(nn, vector<int>(nn, 0));
    
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            newLock[i+m-1][j+m-1] = lock[i][j];
        }
    }
    
    for(int r=0; r<4; r++){
        for(int i=0; i<=nn-m; i++){
            for(int j=0; j<=nn-m; j++){
                auto tempKey = moveKey(newLock, key, i, j, n);
                
                if(isUnlock(tempKey, lock)){
                    return true;
                }
            }
        }
        
        key = rotateKey(key);
    }
    
    return false;
}