[프로그래머스] 2020 KAKAO BLIND RECRUITMENT - 자물쇠와 열쇠, C++

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

프로그래머스

본 문제는 2020 KAKAO BLIND RECRUITMENT 문제로 정답률 7.4%다. 문제를 보면 설명이 좀 길다. 간단하게 설명하면 키를 회전과 이동을 하여 자물쇠의 모든 값이 1인 경우 true를 return하는 문제다. 문제 해결 과정은 다음과 같다.

1. 우선 개인적으로 프로그래머스에서 vector<vector<int>>로 입력되는게 싫다. 따라서 2차원 배열로 값을 저장하였다.
2. cal() 함수를 이용해 키를 회전하였다.
3. 배열의 최대 크기가 20 x 20 이므로 완전 탐색을 실시 하였다.

위의 사진 처럼 값을 비교해야한다. 어떻게 해야할지 고민하다가 lock을 lock.size() + (key.size()-1) * 2의 크기의 배열 가운데에 고정시키고 key를 이동하면서 값을 비교하였다. lock의 모든 값이 1일 때 return answer = true; 아닐 때 키값을 빼면서 모든 경우의 수를 확인했다.

#include <string>
#include <vector>
#include <cstdio>
 
using namespace std;
 
int key_size;
int lock_size;
int d[21][21];
int map[60][60];
int tmp[21][21];
 
 
// 자물쇠의 모든 값이 1인지 확인
bool chk() {
    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 (map[i][j] != 1) return false;
        }
    }
    return true;
}
 
// 키 90도 회전
void cal(int n) {
    if (n == 0) return;
    for (int j = 0; j < key_size; j++) {
        for (int i = 0; i < key_size; i++) {
            tmp[i][key_size-1-j] = d[j][i];
        }
    }
    for (int i = 0; i < key_size; i++) {
        for (int j = 0; j < key_size; j++) {
            d[i][j] = tmp[i][j];
        }
    }
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    key_size = key.size();
    lock_size = lock.size();
    for (int i = 0; i < key_size; i++) {
        for (int j = 0; j < key_size; j++) {
            d[i][j] = key[i][j];
        }
    }
    for (int i = 0; i < lock_size; i++) {
        for (int j = 0; j < lock_size; j++) {
            map[key_size-1+i][key_size-1+j] = lock[i][j];
        }
    }
    for (int t = 0; t < 4; t++) {
        cal(t);
        for (int i = 0; i <= lock_size + (key_size-1)*2 - key_size; i++) {
            for (int j = 0; j <= lock_size + (key_size-1)*2 - key_size; j++) {
                
                for (int x = 0; x < key_size; x++) {
                    for (int y = 0; y < key_size; y++) {
                        map[x+i][y+j] += d[x][y];
                    }
                }
                
                if (chk() == true) return answer = true;
                
                for (int x = 0; x < key_size; x++) {
                    for (int y = 0; y < key_size; y++) {
                        map[x+i][y+j] -= d[x][y];
                    }
                }
 
            }
        }        
    }
    return answer;
}