[Level 3] - 자물쇠와 열쇠

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

프로그래머스

생각해 보기

1. key의 오하단이 lock의 좌상단으로 시작해 key의 좌상단 부분이 lock의 우하단으로 올때까지 모든 경우를 훑으며 내려온다.
2. lock이 0이고 key가 1인 것도 확인해야 하지만, 둘 다 1인 경우 또한 확인해야 한다.
3. key를 오른쪽으로 90도 돌린 뒤 위 과정을 다시 진행한다.
4. 위 과정을 4번 반복하면 된다.

코드

#include <string>
#include <vector>

using namespace std;

bool calc(vector<vector<int>> key, vector<vector<int>> lock){
    int M = key.size(), N = lock.size();
    
    for(int si=-N;si<N;++si){
        for(int sj=-N;sj<N;++sj){
            bool flag = true;
            
            for(int i=0;i<N && flag;++i){
                for(int j=0;j<N && flag;++j){
                    int y = si + i;
                    int x = sj + j;
                    if(!lock[i][j]){
                        if(y>=0 && y<M && x>=0 && x<M)
                            flag = key[y][x];
                            
                        else
                            flag = false;
                    }
                    else{
                        if(y>=0 && y<M && x>=0 && x<M && key[y][x])
                            flag = false;
                    }
                }
            }

            if(flag)
                return true;
        }
    }
    
    return false;
}

vector<vector<int>> turn(vector<vector<int> > key){
    vector<vector<int> > tkey = key;
    int M = key.size();
    
    for(int i=0;i<M;++i){
        for(int j=M-1,tj=0;j>=0;--j, ++tj){
            tkey[i][tj] = key[j][i];
        }
    }
    
    return tkey;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    
    for(int i=0;i<4;++i){
        answer = calc(key, lock);
        
        if(answer)
            return answer;
        key = turn(key);
    }
    return answer;
}