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

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

입력값의 범위가 작기 때문에 완전탐색으로 해결할 수 있는 문제이다.

항상 자물쇠의 크기가 열쇠의 크기 이상이기 때문에 자물쇠를 확장하여서 풀이하였다.

위 그림의 기존의 자물쇠를 가로, 세로로 확장하여 아래의 그림과 같이 만든다.

이 상태에서 열쇠를 회전시켜가며 탐색하면 된다.

위의 그림들과 같은 순서로 모든 지점을 탐색하면 된다. (그림이 너무 많아져서 생략...)

코드

#include <string>
#include <vector>
using namespace std;

// 배열 90도 회전 함수
void rotate(vector<vector<int>>& key) {
    vector<vector<int>> tmp = key;
    for (int i = 0; i < key.size(); i++) {
        for (int j = 0; j < key[i].size(); j++) {
            key[i][j] = tmp[key.size() - 1 - j][i];
        }
    }
}

// 자물쇠가 열리는지 확인해주는 함수
bool isRight(int n, vector<vector<int>>& lock) {
    // 확장된 자물쇠에서 중앙부분만 검사
    for (int i = n; i < 2 * n; i++)
        for (int j = n; j < 2 * n; j++)
            if (lock[i][j] != 1) return false;
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
    // 기존의 자물쇠를 가로, 세로 3배 확장한 자물쇠
    vector<vector<int>> big_lock(lock.size() * 3, vector<int>(lock.size() * 3, 0));
    int n = lock.size();
    int m = key.size();
    // 확장한 자물쇠의 가운데부분을 기존의 자물쇠의 값으로 할당
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            big_lock[n + i][n + j] = lock[i][j];
        }
    }
    for (int r = 0; r < 4; r++) {
        rotate(key);
        for (int a = n - m + 1; a < 2 * n; a++) {
            for (int b = n - m + 1; b < 2 * n; b++) {
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < m; j++) {
                        // 자물쇠에 열쇠를 더해준다
                        big_lock[a + i][b + j] += key[i][j];
                    }
                }
                // 자물쇠가 풀렸는지 검사
                if (isRight(n, big_lock)) return true;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < m; j++) {
                        // 자물쇠가 안풀렸으므로 더했던 값을 다시 빼준다
                        big_lock[a + i][b + j] -= key[i][j];
                    }
                }
            }
        }
    }
    return answer;
}