프로그래머스 - 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT)

이 문제는 brute-force로 쉽게 구할 수 있는 문제였다. 

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
 
void rotate(vector<vector<int>> &key)
{
    queue<int> q;
    for(int i=0; i<key.size(); i++)
        for(int j=0; j<key.size(); j++)
            q.push(key[i][j]);
    for(int i=key.size() - 1; i>=0; i--)
    {
        for(int j=0; j<key.size(); j++)
        {
            key[j][i] = q.front(); 
            q.pop();
        }
    }
}
 
bool solve(vector<vector<int>> key, vector<vector<int>> lock, int hom)
{
    int len = key.size();
    int l_len = lock.size();
    int cnt = 0;
    for(int k = -l_len + 1; k<=l_len; k++)
    {
        for(int l = -l_len + 1; l<=l_len; l++)
        {
            cnt = 0;
            bool flag = true;
            for(int i = 0; i<len; i++)
            {
                if (!flag)
                    break;
                for(int j = 0; j<len; j++)
                {
                    if ((k + i >= 0 && l + j >= 0) && (k + i < l_len && l + j < l_len))
                    {
                        if (key[i][j] == 1 && lock[k + i][l + j] == 0)
                            cnt++;
                        else if (key[i][j] == 1 && lock[k + i][l + j] == 1)
                        {
                            flag = false;
                            break;
                        }
                    }
                }
            }
            if (cnt == hom)
                return true;
        }
    }
    return false;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int hom = 0;
    for(int i=0; i<lock.size(); i++)
        for(int j=0; j<lock.size(); j++)
            if (lock[i][j] == 0)
                hom++;
    for(int i=0; i<4; i++)
    {
        rotate(key);
        if (solve(key, lock, hom))
        {
            answer = true; break;
        }
    }
    return answer;
}

key를 시계방향으로 90도 회전시키는 함수를 구현하고, key와 lock 배열을 비교하면 된다.

 

주의할 점

1) lock 배열 범위 바깥부터 key를 비교해야 한다. 즉, 탐색 범위는 lock 배열의 길이 기준으로 -len ~ len까지가 된다.

2) key의 돌기와 lock의 돌기가 만나면 안된다고 문제에 정의되어 있기 때문에 해당 경우도 처리해주어야 한다. 

3) key의 돌기와 lock의 홈이 만나야 한다.