[Lev.3] 자물쇠와 열쇠(C++)

1. 문제

 

2. 접근 방법

   1. 문제 조건 보면서 범위 줄여가기

        1) 모든 홈이 다 차야 한다 => 홈이 발생한 구역을 구한다. 만약 열쇠 사이즈가 홈 구역보다 작으면 false return(경우의 수가 아예 안만들어 진다.)

        2) 자물쇠의 돌기와 열쇠의 돌기가 맞닿으면 안된다 => 홈이 아닌 부분은 무조건 돌기이다 => 자물쇠의 홈 구역 밖으로 열쇠의 돌기가 있는 경우는 열 수 없음

        3) 자물소의 홈 모양 전체와 열쇠의 돌기 모양 일부가 일치해야 한다.

 

-> 나는 처음에 이렇게 접근했었는데, 이렇게 좁은 범위나 예외 케이스부터 생각하지 말고 큰 관점에서 먼저 생각하는 연습을 하자. 

 

 2. 가장 간단한 방법부터 생각하기

   1) 모든 경우에 대해서 열쇠를 돌려가면서 맞춰본다 -> 완탐 -> 범위를 보니 가능한 복잡도임 

   2) 자물쇠 밖으로도 갈 수 있다 => " 키가 접근할 수 있는 Lock범위를 확장시킨다" 

   3) 키의 모양은 4가지 이므로, 각 4가지 모양을 배열에 저장한 뒤, Lock을 탐색하면서 확인한다. 

 

3. 실수한 부분 & 배운 점

1. 2차원 벡터 확장 & 축소( 가운데로 확장 및 축소하는 법 )

     

* 확장법 

//src벡터를 확장 : des벡터 만들고 src내용 복사
vector<vector<int> > src(3,vector<int>(3,1); // 크기가 3*3이고 초기값이 1인 벡터
vector<vector<int> > des(5,vector<int>(5,0); // 크기가 5*5이고 초기값이 0인 확장할 벡터

for(int i=0;i<3;i++) {
	copy(src[i].begin(),src[i].end(),des[i+1].begin()+1);
  }

   

* 축소법

//src벡터를 축소 : des벡터 만들고 src내용 복사
vector<vector<int> > src(5,vector<int>(5,1); // 크기가 5*5이고 초기값이 1인 벡터
vector<vector<int> > des(3,vector<int>(3,0); // 크기가 3*3이고 초기값이 0인 축소할 벡터

for(int i=1;i<=3;i++) {
	copy(src[i].begin()+1,src[i].end()-1,des[i].begin());
  }

 

2. 확장시킬 때 값은 -1로 초기화 하기. 이 문제에선 0/1 이 각각 홈, 돌기로 의미를 가짐. 따라서 괜히 0이나 1로 확장시켰다간 헷갈릴 수 있으니까 아예 상관 없는 값으로 초기화 하자.

 

3. "전체 홈"을 다 맞춰야 한다. 즉, 탐색을 끝까지 해야 True인지 알 수 있다!!! 나는 계속 M*M사이즈로 자르고 그 안의 홈 개수만 맞추면 True로 리턴해서 고생했었다.. 

 

4. 코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
int tot; // 자물쇠 홈의 개수

//(i,j)를 가장 왼쪽 위 지점으로 하는 M*M 크기의 nLock와 열쇠 모양 확인
bool check(int i, int j, vector<vector<int> > &nLock, vector<vector<int>> *keyArr) {
    int M = keyArr[0].size();
    for(int k= 0;k < 4; k++) {//4가지 모양 중 한 가지 열쇠 모양 선택
        vector< vector<int> > key =keyArr[k];
        int cnt = tot;
        bool flag = true;
        
        for (int ni = 0; ni< M; ni++) {
            for(int nj = 0; nj <M; nj++) {
                int keynum = key[ni][nj];
                int locknum = nLock[i+ni][j+nj];      
                if(locknum + keynum == 2) {
                    flag = false;
                    break;
                }
                else if(locknum == 0 && keynum == 1) cnt--;
            }
           if(!flag ) break;
        }
    if(cnt == 0) return true; //  홈의 총 개수 =  열쇠의 돌기 개수
    }     
    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int M = key.size(),N = lock.size();
    vector<vector<int> >nLock(3*N, vector<int>(3*N,-1)); //크기를 확장한 새로운 lock배열
    
   for(int i=0;i<N;i++) {
        for(int j =0;j<N;j++) {
            if(!lock[i][j]) tot++;
            nLock[N+i][N+j] = lock[i][j];
        }
    }

    //열쇠의 4가지 회전 모양 저장
    vector<vector<int>> keyArr[4];
    keyArr[0] = key;
    for(int idx=1;idx<4;idx++) { 
       vector<vector<int> > v1 = keyArr[idx-1];
       vector<vector<int> > v2(M,vector<int>(M,-1));
        for(int i=0;i<M;i++) {
           for(int j=0;j<M;j++)
               v2[j][M-i-1] = v1[i][j];
        }
        keyArr[idx] = v2; 
    }
    
    // 탐색 시작
    for( int i=1;i<= 2*N;i++) {
        for(int j =1;j<= 2*N; j++) {
            if(check(i,j,nLock,keyArr)) return true;
        }
    }
    return false;
}