자물쇠와 열쇠

코드

#include <string>
#include <vector>
#include <iostream>
// 1055 ~ 1230
using namespace std;

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int tot_cnt = 0;
    for(int r=0;r<lock.size();r++)
        for(int c=0;c<lock.front().size();c++)
            if(lock[r][c] == 0) tot_cnt++;
    /* 4번 회전 해야 모든 상태 검사 가능 */
    for(int n=0;n<4;n++)
    {
        vector<vector<int>> tmp(key.begin(), key.end());
        int cur_c = key.front().size();
        for(int a=0;a<key.size();a++)
        {
            cur_c--;
            for(int b=0;b<key[a].size();b++)
                tmp[b][cur_c] = key[a][b];
        }
        key = tmp;
        int st_r = -lock.size()+1;
        int st_c = -lock.front().size()+1;
        /* 방향을 움직이며 키가 조건에 부합한지 검사 */
        for(int dr=st_r;dr<(int)lock.size();dr++)
        {
            for(int dc=st_c;dc<(int)lock.front().size();dc++)
            {
                bool flag = true;
                int cnt = 0;
                for(int r=0;r<key.size();r++)
                {
                    for(int c=0;c<key.front().size();c++)
                    {
                        int nr = r + dr;
                        int nc = c + dc;
                        if(nr<0 or nc<0 or nr>=lock.size() or nc>=lock.front().size()) continue;
                        // 0=0 or 1=1
                        if(key[r][c] == lock[nr][nc]) goto stop;
                        // 1,0
                        if(key[r][c] == 1) cnt++;
                    }
                }
                stop:;
                if(cnt == tot_cnt) {
                    return true;
                }
            }
        }
    }
    return false;
}

• 핵심
  • 자물쇠의 총 구멍 개수(tot_cnt)를 구해서 열쇠로 매운 개수(cnt)와 비교해서 같은 경우에만 true!
    --> 현재 key로 일부분은 채워질 수 있지만, 반드시 정답은 모든 자물쇠 구멍을 채워야 하기 때문
  • 이동하는 좌표를 구할 때 행,열 간 차이를 나타내는 dr / dc의 초기 값을 (-N+1)으로 설정
    --> key를 오른쪽 / 아래 방향 뿐만 아니라 위/ 왼쪽 방향으로도 옮길 수 있기 때문!