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

풀이)

완전탐색문제이다.

key는 회전과 상하좌우 이동이 가능하다.

키가 자물쇠에 맞는지만 확인하면 되니깐, 회전은 오른쪽 회전만 다루도록 하겠다.

키의 이동이 관건인데,

이는 키가 자물쇠의 끝에서부터 걸쳐서 확인해보는 방법으로 해결하면 된다.

열쇠의 가장 오른쪽 아랫부분과 자물쇠의 가장 위쪽 부분을 맞추는 경우부터

열쇠의 가장 왼쪽 윗부분과 자물쇠의 가장 오른쪽 아래 부분을 맞추는 경우까지를 모두 해준다.

lock의 크기 N + (key의 크기 M - 1)*2 범위를 map이라고 칭하겠다.

키를 이동시키면서 그 때의 키가 걸쳐있는 범위의 map 값을 변화시킨다.

map

map 값이 0이면 -> 열쇠의 돌기와 자물쇠의 홈이 일치안함 , 2이면 -> 열쇠의 돌기와 자물쇠의 돌기가 일치해버림

이므로, 0과 2가 나오면 그 경우는 실패했다고 생각하면된다,

코드)

#include <string>
#include <vector>
#include<iostream>
using namespace std;

bool check(int y,int x,vector<vector<int>>key,vector<vector<int>>map,int locksize){
   //map과 key가 겹치는 부분 더함
    for (int ny=y; ny < y + key.size(); ny++) {
        for (int nx = x; nx <x + key.size(); nx++) {
            map[ny][nx] += key[ny-y][nx-x];
        }
    }

    //map 가운데 lock 자물쇠의 값 확인
    for(int i=0;i<locksize;i++){
        for(int j=0;j<locksize;j++){
            if(map[i+key.size()-1][j+key.size()-1] == 1)continue;
            return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    //회전 - 오른쪽 회전-> 90도, 180도, 270도, 360도 4번
    //이동 - 오른쪽, 왼쪽, 위, 아래
    int mapsize = lock.size()+ (key.size()-1 )*2;
    vector<vector<int>> map(mapsize,vector<int>(mapsize,0));
    //가운데에 lock두기
    for(int i=0;i<lock.size();i++){
        for(int j=0;j<lock.size();j++){
            map[i+key.size()-1][j+key.size()-1] = lock[i][j];
        }
    }

    //모든 경우 확인
    //90도씩 4번 회전
    for (int i=0; i<4; i++) {
        // key를 전체 map에 대해 탐색
        for (int y = 0; y < mapsize - key.size()+1; y++) {
            for (int x = 0; x < mapsize - key.size()+1; x++) {
                if (check(y, x, key, map ,(int)lock.size())) {
                    answer = true;
                    return answer;
                }
            }
        }
        //key회전
        vector<vector<int>> temp = key;
        int idx = key.size() -1;
        for(int i=0;i<key.size();i++){
            for(int j=0;j<key.size();j++){
                key[j][idx] = temp[i][j];
            }
            idx--;
        }
    }
    return answer;
}