[Programmers 문제 풀이] 자물쇠와 열쇠

안녕하세요. 이번 포스팅에서는 Programmers 문제인 자물쇠와 열쇠 문제를 풀어보겠습니다.

 

해당 문제는 아래의 링크에서 확인하실 수 있습니다.

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

코딩테스트 연습 - 자물쇠와 열쇠

 

단순한 완전 탐색 문제입니다.

 

Key를 90도로 네 번 회전하는 경우의 수 ->

각 Key마다 Key의 오른쪽 아래의 끝점이 lock배열의 왼쪽 맨 위에 접하는 부분부터 

각 Key의 왼쪽 위 끝점이 lock 배열의 오른쪽 맨 아래에 접하는 부분까지 모든 경우를 탐색해주시면 됩니다.

 

주의하실 점이 

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

 

라는 문구인데, 쉽게 생각하면, Key가 1이고 Lock이 1이면 안됩니다. 해당 경우의수가 포함된 case는 정답이 될 수 없습니다.

 

<소스 코드>

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

using namespace std;

vector<vector<int>> rotate90(vector<vector<int>>& key) {
    int m = key.size();
    vector<vector<int>> ret(m, vector<int>(m));
    
    for(int i = 0; i < key.size(); i++) {
        for(int j = 0; j < key[i].size(); j++) {
            ret[i][j] = key[j][m-i-1];
        }
    }
    return ret;
}
bool unlock(int y, int x, vector<vector<int>>& key, vector<vector<int>> lock) {
    int keySize = key.size(), lockSize = lock.size();
    for(int i = 0; i < keySize; i++) {
        for(int j = 0; j < keySize; j++) {
            if(key[i][j]==1 && i+y < lockSize && j+x < lockSize
              && i+y >= 0 && j+x >= 0 ){
                if(lock[i+y][j+x]==0) lock[i+y][j+x]=1;
                else return false; // 이 부분 유의!
            } 
            
        }
    }
    
    for(int i = 0; i < lockSize; i++) {
        for(int j = 0; j < lockSize; j++) {
            if(lock[i][j]==0) return false;
        }
    }
    return true;
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int n = lock.size(), m=key.size();
    for(int i = 0; i < 4; i++) {
        key = rotate90(key);
        for(int j = -m+1; j < n; j++) {
            for(int k = -m+1; k < n; k++) {
                if(unlock(j, k, key, lock)) {
                    return true;
                }    
            }
        }
    }
    return false;
}

 

 

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.