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

 이 문제는 구현이 매우 어려운 문제였다. 일단 입력이 매우 작아 이차원 배열 최대 크기가 400이고, 400 ^ 3 까지도 가능할 정도로 넉넉한 알고리즘을 짤 수 있다는 얘기이다. 이 문제에서 핵심은 키와 자물쇠를 대볼때, 키의 인덱스와 자물쇠의 인덱스가 다르다는 것이다. 이를 해결하기 위해 dy와 dx를 생각했고, 이는 자물쇠의 y, x 좌표와 키의 y, x 좌표가 얼만큼 차이나는지를 나타낸다. 처음에는 예시에 따라 dy와 dx의 값 범위를 -M과 M 사이로 했는데, 이렇게 하면 세어지지 않는 범위가 생긴다. 이는 키의 길이가 더 짧을 수 있기 때문이다. 그래서 inRange 함수로 어차피 범위에 없으면 아예 세지 않기 때문에, 넉넉하게 -N부터 N까지를 세도록 했고, 정답을 받을 수 있었다.

 

 

 이 문제를 풀면서 실제 코딩 테스트에 이런 문제가 나오면 절대 못 풀것 같다는 생각이 들었다. 어려운 구현 문제도 꾸준히 풀어줘야겠다는 생각이 들었다.

 

 

#include <string>
#include <vector>

using namespace std;

int N, M;

bool inRange(int y, int x) {
    if (0 <= y && y < M && 0 <= x && x < M) {
        return true;
    }
    return false;
}

vector<vector<int>> roll(vector<vector<int>>& key) {
    
    vector<vector<int>> result;
    
    for (int x = M - 1; x >= 0; x--) {
        vector<int> temp;
        for (int y = 0; y < M; y++) {
            temp.push_back(key[y][x]);
        }
        
        result.push_back(temp);
    }
    
    return result;
}

int hole;

bool solve(vector<vector<int>>& key, vector<vector<int>>& lock) {
    for (int dy = -N; dy <= N; dy++) {
        for (int dx = -N; dx <= N; dx++) {
            int temp = 0;
            bool flag = true;
            
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    if (inRange(y + dy, x + dx)) {
                        if (key[y + dy][x + dx] == 1 && lock[y][x] == 0) {
                            temp++;
                        }
                        if (key[y + dy][x + dx] == 1 && lock[y][x] == 1) {
                            flag = false;
                        }
                    }
                }
            }
            
            if (temp == hole) {
                if (flag) {
                    return true;
                }
            }
        }
    }
    
    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    
    M = key.size();
    N = lock.size();

    int keyEdge = 0;
    
    for (vector<int>& k : key) {
        for (int t : k) {
            if (t == 1) {
                keyEdge++;
            }
        }
    }
    
    for (vector<int>& l : lock) {
        for (int t : l) {
            if (t == 0) {
                hole++;
            }
        }
    }
    
    if (keyEdge == 0 && hole == 0) {
        return true;
    }
    
    if (keyEdge != 0 && hole == 0) {
        return true;
    }
    
    if (keyEdge == 0 && hole != 0) {
        return false;
    }
    
    if (solve(key, lock)) {
        return true;
    }
    
    key = roll(key);
    if (solve(key, lock)) {
        return true;
    }
    
    key = roll(key);
    if (solve(key, lock)) {
        return true;
    }
    
    key = roll(key);
    if (solve(key, lock)) {
        return true;
    }
    
    return answer;
}