(프로그래머스 c++ KAKAO)자물쇠와 열쇠

programmers.co.kr/learn/courses/30/lessons/60059#

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

 

완전 탐색으로 답이 있을 때까지 찾아야 한다.

답이 없으면 false를 리턴.

 

N = 자물쇠의 크기, M = 열쇠의 크기

우선 키를 4가지의 형태로 준비한다.

원래의 키 형태와 90도, 180, 270도를 돌린 키를 keys 배열에 저장한다.

 

그리고 자물쇠를 80 * 80 2차원 벡터 board에 다시 저장한다.

열쇠를 돌려가면서 열리는지 확인하기 위함이다.

자물쇠의 시작 인덱스는 board[M - 1][M - 1]이다.

아래 그림은 자물쇠를 board에 옮겼을 때 결과이다.

자물쇠는 주황색 테두리로 표시한 부분이며,

빨간색 테두리는 4개의 열쇠 모양이 탐색할 공간이다.

dfs를 통해 board[0][0] ~ board[N + M - 2]를 시작 인덱스로 잡아 탐색한다.

dfs는 내부적으로 키 4개의 모양을 돌아야 한다.

또한, 탐색을 할 때 열쇠의 돌기와 자물쇠의 돌기가 만나지 않는 조건도 필요하다.

 

열쇠의 0인 부분과 자물쇠의 1인 부분이 만나면 카운트를 해주면서

해당 열쇠의 모양이 자물쇠를 열 수 있는지 확인을 한다.

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

using namespace std;

int lockZeroCount = 0;
int N = 0;
int M = 0;
vector<vector<int>> board(80, vector<int>(80, 1));
vector<vector<vector<int>>> keys(4, vector<vector<int>>(20, vector<int>(20, 0)));

void rotateKey(int current){
    for(int i = 0; i < M; i++){
        for(int j = 0; j < M; j++){
            keys[current][i][j] = keys[current - 1][M - j - 1][i];
        }
    }
}

bool dfs(int x, int y){
    int range[2] = {M - 1, N + M - 2};
    
    for(int i = 0; i < 4; i++){
        int count = 0;
        bool keep = true;
        
        for(int j = 0; j < M; j++){
            for(int k = 0; k < M; k++){
                if(board[x + j][y + k] && keys[i][j][k]){
                    if(x + j >= range[0] && x + j <= range[1] && y + k >= range[0] && y + k <= range[1]){
                        keep = false;
                        break;
                    }
                    continue;
                }
                
                if(!board[x + j][y + k] && keys[i][j][k]){
                    count++;
                }
            }
            if(!keep){
                break;
            }
        }
        
        if(count == lockZeroCount){
            return true;
        }
    }
    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    N = lock.size();
    M = key.size();
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(lock[i][j] == 0){
                lockZeroCount++;
                board[M - 1 + i][M - 1 + j] = lock[i][j];
            }
        }
    }
    
    keys[0] = key;
    
    //90도씩 회전한 키 저장(총 4개)
    for(int i = 1; i < 4; i++){
        rotateKey(i);
    }
    
    for(int i = 0; i < N + M - 1; i++){
        for(int j = 0; j < N + M - 1; j++){
            if(dfs(i, j)){
                return true;
            }
        }
    }
    
    return false;
}