프로그래머스: 자물쇠와 열쇠

문제:

1.열쇠는 회전과 이동이 가능

2.자물쇠의 모든 홈을 채워야함.

 

2차원 배열 key /// 2원 배열 lock

 

열수 있으면 true// 없으면 false 

 

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다. ( M<=N)
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

---

풀이:

 

완전탐색으로 풀경우 시간복잡도 = 90도 회전한 모양 4가지*(N+M+N)*(N+M+N)칸의 갯수 * 4(위,아래,오,왼) 

최대 4*(60)*(60)*4 = 57,600 번만 해보면됨.

 

충분할것 같음.

 

 

먼저.

1. 90 도 회전한 모양 4가지를 만들었다.

2. 각 모양에서 1의 위치를 0,0 의 상대 위치로 pair 벡터로 저장해 주었다.

3. 0~key_size+ lock_size 까지 for문을 차례 차례 돌면서  pair벡터에 있던 값들을 넣어주고 빼주고 하면서 정답을 찾았다.

---

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int key_size, lock_size,allsize;

vector<pair<int,int>> print_v(vector<vector<int>> &temp){
    vector<pair<int,int> > a;
    for(int i=0; i<temp.size(); i++){
        for(int j=0; j<temp[i].size(); j++){
            if(temp[i][j]==1){
                a.push_back(make_pair(i,j));
            }
        }
    }
    return a;
}

vector<vector<int>> turn(vector<vector<int> > &key){
    int key_size= key.size();
    vector<vector<int> > temp(key_size, vector<int>(key_size));

    for(int x=0; x<key_size; x++){
        for(int y=0; y<key_size; y++){
            temp[y][(key_size-1) - x] = key[x][y];
        }
    }
    return temp;
}

bool check(vector<vector<int> > &map){
    for(int i= key_size ; i<key_size+lock_size; i++){
        for(int j= key_size; j<key_size+lock_size; j++){
            if(map[i][j]!=1) return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    key_size = key.size();
    lock_size = lock.size();
    allsize = 2*key_size+ lock_size;
    vector< vector<int> > map(allsize, vector<int>(allsize));
    for(int i= 0; i<lock_size; i++){
        for(int j = 0; j<lock_size; j++){
            map[i+key_size][j+key_size] = lock[i][j];
        }   
    }
    vector< vector< pair<int,int> > > keys;

    keys.push_back(print_v(key));
    for(int i=0; i<3; i++){
        key = turn(key);
        keys.push_back(print_v(key));
    }
    for(int k =0 ; k<keys.size(); k++){
        for(int i=0; i<=key_size+lock_size; i++){
            for(int j=0; j<=key_size+lock_size; j++){
                for(int g=0; g<keys[k].size(); g++){
                    pair<int,int> a = keys[k][g];
                    int x = a.first + i;
                    int y = a.second + j;
                    if(map[x][y]==0){
                        map[x][y] =1;
                    }else{
                        map[x][y] =2;
                    }
                }
                if(check(map)) return true;
                for(int g=0; g<keys[k].size(); g++){
                    pair<int,int> a = keys[k][g];
                    int x = a.first + i;
                    int y = a.second + j;
                    if(map[x][y]==2){
                        map[x][y] =1;
                    }else if(map[x][y] ==1){
                        map[x][y] = 0;
                    }
                }
            }
        }
    }
    return answer;

}

이렇게 쉬운걸,,, 그때는 왜 못풀었을까 ,,,,,,, ㅠㅠ