[프로그래머스]level.3 - 자물쇠와 열쇠(C++)

문제

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

프로그래머스

문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

---

입출력 예

key	lock	result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

입출력 예에 대한 설명

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

 

내 풀이

중요한 포인트

1. lock과 key를 편하게 비교할 수 있게 배열을 key.size()-1만큼 확장한다.

2. 비교 범위를 줄여 반복문을 최대한 덜 돌게 한다.

3. 범위 내에서 키를 4회전하며 비교한다.

#include <string>
#include <vector>
#include <limits>

using namespace std;

bool isMatch(const vector<vector<int>>& map, const vector<vector<int>>& key, int row, int col, int count);
void RotateKey(vector<vector<int>>& key);

bool solution(vector<vector<int>> key, vector<vector<int>> lock) 
{
    int key_size = key.size() - 1;
    int map_size = lock.size() + 2 * key_size;
    
    // 키의 크기만큼 여유있게 배열을 확장한다.
    vector<vector<int>> map(map_size, vector<int>(map_size, -1));

    // 홈 개수
    int concave_count = 0;

    int imin = std::numeric_limits<int>::min();
    int imax = std::numeric_limits<int>::max();
    
    // 탐색 범위
    int search_range_row[] = { imax, imin };
    int search_range_col[] = { imax, imin };

    for (int c = 0; c < lock.size(); ++c)
    {
        for (int r = 0; r < lock.size(); ++r)
        {
            int newRow = key_size + r;
            int newCol = key_size + c;

            // 자물쇠를 map에 채우기
            map[newCol][newRow] = lock[c][r];

            if (lock[c][r] == 0)
            {
                ++concave_count;
                
                // 탐색 범위 조정
                if (newRow < search_range_row[0])
                    search_range_row[0] = newRow;

                if (newRow > search_range_row[1])
                    search_range_row[1] = newRow;

                if (newCol < search_range_col[0])
                    search_range_col[0] = newCol;

                if (newCol > search_range_col[1])
                    search_range_col[1] = newCol;

            }
        }
    }

    // 홈이 없으면 키와 상관없이 열 수 있다.
    if (concave_count == 0)
        return true;

    // 시작 위치 key 사이즈에 따라 조절
    search_range_row[0] -= key_size;
    search_range_col[0] -= key_size;

    
    // 탐색 범위 내에서 키를 4회전 하면서 찾기
    for (int t = 0; t < 4; ++t)
    {
        for (int col = search_range_col[0]; col <= search_range_col[1]; ++col)
        {
            for (int row = search_range_row[0]; row <= search_range_row[1]; ++row)
            {
                if (isMatch(map, key, row, col, concave_count))
                    return true;
            }
        }

        RotateKey(key);
    }

    return false;
}

// 키 회전
void RotateKey(vector<vector<int>>& key)
{
    vector<vector<int>> tmp(key.size(), vector<int>(key.size(), 0));

    for (int y = 0; y < key.size(); ++y)
        for (int x = 0; x < key.size(); ++x)
        {
            tmp[y][x] = key[key.size() - x - 1][y];
        }

    key = tmp;
}

// 키와 자물쇠가 맞는지 확인한다.
bool isMatch(const vector<vector<int>>& map, const vector<vector<int>>& key, int row, int col, int count)
{
    for (int c = col; c < col + key.size(); ++c)
    {
        for (int r = row; r < row + key.size(); ++r)
        {
            // 둘 다 돌기인 경우
            if (map[c][r] == 1 && key[c - col][r - row] == 1) 
                return false;
            
            // 둘 다 홈인 경우
            if (map[c][r] == 0 && key[c - col][r - row] == 0) 
                return false;

            // 자물쇠는 홈이고 열되는 돌기인 경우
            if (map[c][r] == 0 && key[c - col][r - row] == 1) 
                --count;
        }
    }
    
    // 모든 홈이 채워졌다면
    if (count == 0)
        return true;

    return false;
}