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

프로그래머스 자물쇠와 열쇠 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60059

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

문제 풀이

• 이 문제는 2차원 Array를 다루는 문제입니다. 
• key를 90도 씩 회전하면서 lock 위를 슬라이딩 하여 lock을 모두 채우는 경우가 있으면 true를 반환합니다. 
• key를 슬라이딩 하는 방법은 다음 그림과 같습니다. (2*M + N - 2) 사이즈의 Array를 하나 선언하여 가운데에 lock영역을 두고(3번) key를 처음부터(1번) 마지막까지(2번) 이동하면서 lock 영역이 모두 1으로 채워지는 경우가 있다면 자물쇠가 열리는 것입니다. 

• 문제를 풀다보면 2d(정사각) array를 90도 회전해야 하는 경우가 종종 있습니다. 코드가 어렵지 않으니 외워두시면 다른 문제에도 유용하게 사용하실 수 있습니다.

void mat_rotate(vector<vector<int>> &mat) {
    int M = mat.size();
    vector<vector<int>> temp(M, vector<int>(M));
    
    for(int i=0; i<M; ++i) {
        for(int j=0; j<M; ++j) {
            temp[i][j] = mat[M-(j+1)][i];
        }
    }
    
    mat = temp;
}

코드

#include <string>
#include <vector>

using namespace std;

int K, L, B;

void rotate_key(vector<vector<int>> &key) {
    vector<vector<int>> tmp(K, vector<int>(K, 0));
    for(int i=0; i<K; ++i) {
        for(int j=0; j<K; ++j) {
            tmp[i][j] = key[K-(j+1)][i];
        }
    }
    
    key = tmp;
}

bool check(vector<vector<int>> &board, vector<vector<int>> &key, int y, int x) {
    bool ret = true;
    for(int i=0; i<K; ++i) {
        for(int j=0; j<K; ++j) {
            board[i+y][j+x] += key[i][j];
        }
    }
    
    // 가운데 lock 영역이 모두 1이면 true, 아니면 false
    for(int i=0; i<L; ++i) {
        for(int j=0; j<L; ++j) {
            if(board[i+K-1][j+K-1] != 1) {
                ret = false;
                break;
            }
        }
    }    
    
    for(int i=0; i<K; ++i) {
        for(int j=0; j<K; ++j) {
            board[i+y][j+x] -= key[i][j];
        }
    }
    
    return ret;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    K = key.size(), L = lock.size();
    B = 2*(K-1) + L;
    
    vector<vector<int>> board(B, vector<int>(B, 0));
    
    // 가운데에 lock 영역 두기 (3번)
    for(int i=0; i<L; ++i) {
        for(int j=0; j<L; ++j) {
            board[i+K-1][j+K-1] = lock[i][j];
        }
    }    
    
    for(int r=0; r<4; ++r) { // key 4번 회전
        for(int i=0; i<=B-K; ++i) { // key를 처음부터 끝까지 슬라이딩 (1, 2번)
            for(int j=0; j<=B-K; ++j) {
                if(check(board, key, i, j)) return true;
            }
        }
        
        rotate_key(key);
    }
    
    return false;
}

실행 결과