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

문제 링크 : programmers.co.kr/learn/courses/30/lessons/60059

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

문제 유형

Brute Force, 구현

 

[2020 카카오 블라인드 코딩 테스트]

key와 lock의 크기가 작으므로, 모든 경우를 탐색함으로써 자물쇠를 열 수 있는 경우를 찾아내는 문제이다.

key의 일부분만으로 lock을 맞춰도 관계없으므로, key의 가능한 모든 위치를 계산하기 위해 lock을 3배의 크기로 확장하여 구현한다. (코드의 extend_lock)

key를 회전하는 함수와, key와 lock의 돌기가 맞물리면 안 된다는 조건에 주의하며 구현에 신경쓰면 된다.

 

[코드]

#include <string>
#include <vector>
 
using namespace std;
typedef pair<int, int> p;
int locksize, keysize;
 
vector<vector<int>> rotate_key(vector<vector<int>> key){
    //key 회전함수
    vector<vector<int>> ret;
    vector<int> temp;
    for(int i = 0; i < keysize; i++){
        temp.clear();
        for(int j = keysize - 1; j >= 0; j--){
            temp.push_back(key[j][i]);
        }
        ret.push_back(temp);
    }
    return ret;
}
 
bool match(vector<vector<int>> key, vector<vector<int>> lock, p startpos){
    //key의 맨 왼쪽 맨 위의 좌표를 startpos로 할 때, key와 lock을 맞춰보기
    int row = startpos.first, col = startpos.second;
    
    //key와 lock 맞춰보기
    for(int i = row; i < row + keysize; i++)
        for(int j = col; j < col + keysize; j++){
            if(key[i - row][j - col] == 1) {
                if(lock[i][j] == 1) return false;   //돌기끼리 만난다면 false
                lock[i][j] = 1;
            }
        }
    
    //원래 lock의 위치부터 모든 칸이 채워졌는지 검사
    for(int i = locksize; i < locksize * 2; i++)
        for(int j = locksize; j < locksize * 2; j++)
            if(lock[i][j] == 0) return false;   //비는 칸이 있다면
    
    return true;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    locksize = lock.size();
    keysize = key.size();
    
    //lock 배열 확장 : 가로, 세로 3배 크기로
    vector<vector<int>> extend_lock(locksize * 3, vector<int>(locksize * 3, 0));
    for(int i = locksize; i < locksize * 2; i++)
        for(int j = locksize; j < locksize * 2; j++)
            extend_lock[i][j] = lock[i - locksize][j - locksize];
 
    for(int r = 0; r < 4; r++){
        //회전횟수 : 3
        //시작점 옮겨가며 모든 경우를 확인
        for(int i = 0; i <= locksize * 2; i++){
            for(int j = 0; j <= locksize * 2; j++){
                bool res = match(key, extend_lock, {i, j});
                if(res) return true;
            }
        }
        key = rotate_key(key);    
    }
    
    
    return false;
}