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

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

풀이

N <= 20으로 상당히 작은 값이기 때문에 모든 경우를 확인해서 문제를 풀어도 된다.

따라서 key와 lock의 겹치는 부분이 오른쪽 아래의 한 칸인 경우부터 왼쪽 위의 한 칸인 경우까지 모두 확인한다.

이때 for문의 범위가 조금 많이 헷갈려서 key의 맨 왼쪽 위 칸의 위치를 기준으로 생각해 범위를 정하였다.

key가 각각의 위치와 회전에 대해서 check()함수를 호출하여 자물쇠를 열 수 있는지 확인하고 열 수 있는 경우 true를 반환한다.

check()함수에서는

1. 비교하는 위치가 lock의 범위 밖인 경우엔 continue하여 비교하지 않게 한다.
2. 만약 비교하는 위치의 값이 서로 동일하다면 key로 자물쇠를 열 수 없는 경우이기 때문에 false를 반환한다.
3. 만약 비교하는 위치의 lock은 0, key는 1인 경우엔 열쇠가 들어가는 위치이므로 check++해준다.
4. for문을 모두 완료한 후 매개변수로 받아온 lock의 빈칸 개수인 cnt와 check값이 동일한지 확인하고 동일한 경우에만 true를 반환한다. 

 

#include <string>
#include <vector>

using namespace std;

bool check(int cnt, int r, int c, vector<vector<int>> key, vector<vector<int>> lock){
    bool can = true;
    int check = 0;
    int key_size = key.size();
    int lock_size = lock.size();

    for(int i=r; i<r+key_size; i++){
        for(int j=c; j<c+key_size; j++){
            
            if(i<0 || j<0 || i>=lock_size || j>= lock_size)
                continue;
            
            //열쇠구멍이랑 안맞음
            if(lock[i][j] == key[i-r][j-c]){
                can = false;
                return can;
            }
            //맞는 구멍수 count
            else if(lock[i][j] == 0 && key[i-r][j-c] == 1)
                check++;
        }
    }
    //열쇠칸에 자물쇠 빈칸 수가 안 맞음
    printf("%d %d\n", check, cnt);
    if(check!= cnt)
        can = false;
    return can;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int key_size = key.size();
    int lock_size = lock.size();
    int cnt = 0;
    
    vector<vector<int>> temp;
    //temp 크기
    temp.resize(key_size);
    for(int i=0; i<key_size; i++)
        temp[i].resize(key_size);
    
    //자물쇠의 빈칸 count
    for (int i=0; i<lock_size; i++){
        for(int j=0; j<lock_size; j++){
            if(lock[i][j] == 0)
                cnt++;
        }
    }
    if(cnt == 0)
        return true;
    //모든 위치에 대해서
    for (int i=-key_size+1; i<lock_size; i++){
        for(int j=-key_size+1; j<lock_size; j++){
            //키 4방향 돌리기
            for(int k=0; k<4; k++){
                //90도 회전해 temp에 저장했다가 다시 key에 저장
                for(int l = 0; l < key_size; l++){
    	            for(int m = 0; m < key_size; m++){
        	            temp[m][key_size-l-1] = key[l][m];
                    }
                }
                for(int l = 0; l < key_size; l++){
    	            for(int m = 0; m < key_size; m++){
        	            key[l][m] = temp[l][m];
                    }
                }
                
                //check함수 호출해 열 수 있는지 확인
                if(check(cnt, i, j, key, lock) == true){
                    answer = true;
                    return answer;
                }
            }
            
        }
    }
    
    return answer;
}