[알고리즘] 2020 카카오 기출 _ 자물쇠와 열쇠

문제

2020 KAKAO BLIND RECRUIT : 자물쇠와 열쇠

구상

열쇠는 회전과 이동이 가능하고, 열쇠로 자물쇠를 열수 있는지를 판단하는 문제이니, 완전 탐색으로 풀 수 있지 않을까?

불가능 조건?

1. 자물쇠의 홈이 열쇠의 돌기보다 많을 경우
2. 열쇠를 360도 회전시키며 자물쇠의 패턴과 비교할때, 1바퀴를 회전해도 불가능할 경우

패턴 확인을 어떻게 할 것인가?

lock을 순회하면서 현재 key와 비교하며 조건을 만족하는지 확인한다.

시간복잡도?

key는 M x M (3<= M <=20), lock은 N x N(2 <= N <= 20) 2차원 배열이므로
탐색의 최대값은 20^4 = 16만이므로 완전탐색이 가능하다!

코드

#include<bits/stdc++.h>
using namespace std;

//// key를 시계방향 90도 회전
void rotateKey(vector<vector<int>> &key){
    int m = key.size();
    vector<vector<int>> temp(m,vector<int>(m,0));
    for(int j=0; j<m; j++){
        for(int i=m-1; i>=0; i--){
            temp[j][m-i-1] = key[i][j];
        }
    }
    key = temp;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int m=key.size(),n=lock.size(),cnt = 0;
    // lock의 홈의 갯수 count
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(lock[i][j]==0){
                ++cnt;
            }
        }
    }
    // key를 회전시키며 탐색
    for(int k=0; k<4; k++){
        rotateKey(key); // key 회전
        for(int i=-m+1; i<n; i++){
            for(int j=-m+1; j<n; j++){
                int check = 0;
                for(int y=0; y<m; y++){
                    for(int x=0; x<m; x++){
                        int ny = y+i;
                        int nx = x+j;
                        // lock 의 범위를 벗어나면 continue
                        if(ny<0 || ny>=n || nx<0 || nx>=n) continue;
                        // key와 lock이 매칭되지 않으면 더 이상 탐색할 필요가 없으니 break
                        if(key[y][x]==lock[ny][nx]){
                            break;
                        }
                        // key로 메울수 있는 홈의 갯수를 count
                        if(key[y][x]==1 && lock[ny][nx]==0){
                            ++check;
                        }
                    }
                }
                // 메운 홈이 lock의 홈 갯수와 동일하다면 true 반환
                if(check==cnt){
                    return true;
                }
            }
        }
    }
    // 채울 수 없으면 false 반환
    return false;
}

key 를 시계방향으로 90도 회전시킨 후, lock을 탐색하여 해결조건을 확인한다.

주의할 점

탐색 범위

맨 처음 탐색의 범위를 0 <= i <n , 0 <= j <n 으로 설정하여 통과하지 못했다.
하지만 문제 조건을 잘 살펴보면

탐색의 시작이 lock 바깥에서부터 시작할 수 있다는 것을 확인할 수 있다.

고로 탐색 범위를 -m+1 <= i <n , -m+1 <= j <n 으로 설정해주어야지 가능한 모든 경우의 수를 탐색 할 수 있으니 주의하자.

vector 초기화

2차원 vector를 index로 접근할것이기 때문에, 선언 후 초기화를 반드시 진행해주어야 한다.

일반적인 vector 초기화

// n의 크기를 가지는 vector 0으로 초기화
vector<int>v(n,0);

이를 동일하게 2차원 vector로 확장하면

2차원 vector 초기화

// n*n의 크기를 가지는 2차원 vector 0으로 초기화
vector<vector<int>>v(n,vector<int>(n,0));