(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 자물쇠와 열쇠

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

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

구현 문제였습니다.

 

풀이방법

검은색 부분은 key이고 파란 부분은 lock입니다. 계속해서 오른편으로 이동하고 끝에 다다르면 한 칸 내려가 처음부터 시작해 다시 오른쪽으로가는 방법으로 열 수 있는지의 여부를 알아낼 수 있습니다.

 

1. expandedLock 배열을 만들어 lock을 50 * 50으로 넉넉하게 확장해줍니다. 그리고 (20 ~ 20 + 행)부터 (20번째 열 ~ 20 + lock.size()번째 열)까지 기존에 있던 lock을 해당 열에 복사해줍니다.

 

2. 매번 key비교하기 전 원본을 미리 다른 배열에 복사해줍니다. 그 후 (20 ~ 20 + 행)부터 (20번째 열 ~ 20 + lock.size()번째 열) 안에 있는 유효한 좌표에 있다면 다음과 같이 유효한 key인지 검사해야합니다.

 2-1. key가 0, lock이 0이거나 둘다 1이라면 유효한 key가 아닙니다. 따라서 루프를 탈출해줍니다.

 2-2. key가 1이고 lock이 0인 부분에만 맞춰줄 수 있으므로 이 경우에는 해당 lock에 맞춰서 1로 만들어줍니다.

 2-3. 성공적으로 모두 1이 되었다면 true를 반환합니다.

 

3.모든 경우를 해봤을 때 열 수 없으므로 flase를 반환합니다.

 

Code

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

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

void copyLock(int lock[50][50], int expandedLock[50][50]){
    for(int i = 0; i < 50; i++)
        for(int j = 0; j < 50; j++)
            lock[i][j] = expandedLock[i][j];
}

bool canOpen(int lock[50][50], int n){
    for(int i = 20; i < 20 + n; i++)
        for(int j = 20; j < 20 + n; j++)
            if(!lock[i][j]) return false;
    return true;
}

bool isSafeRange(int i, int j, int r, int c, int n){
    if(20 <= i + r && i + r < 20 + n && 20 <= j + c && j + c < 20 + n) return true;
    return false;
}


bool validCheck(vector<vector<int>>key, int expandedLock[50][50], int n){
    int lock[50][50];

    for(int r = 0; r < 50; r++){
        for(int c = 0; c < 50; c++){
            copyLock(lock, expandedLock);
            for(int i = 0; i < key.size(); i++){
                for(int j = 0; j < key.size(); j++){
                    if(!isSafeRange(i,j,r,c,n)) continue;
                    if(!key[i][j] && !lock[i+r][j+c] || key[i][j] && lock[i+r][j+c]) break;
                    if(key[i][j] == 1 && !lock[i+r][j+c]) lock[i+r][j+c] = 1;
                }
            }   
            if(canOpen(lock, n)) return true;
        }
    }

    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    int expandedLock[50][50] = {0};

    for(int i = 0; i < lock.size(); i++)
        for(int j = 0; j < lock.size(); j++)
            expandedLock[i + 20][j + 20] = lock[i][j];

    
    for(int i = 0; i < 4; i++){
        if(validCheck(key, expandedLock, lock.size())) {answer = true; break;}
        rotateKey(key);
    }

    return answer;
}