자물쇠와 열쇠 [Lv. 3]

프로그래머스

N * N 크기의 자물쇠와 M * M 크기의 열쇠가 있습니다. 열쇠가 자물쇠를 열 수 있는지 확인해주세요.

이때 M은 항상 N이하이며 자물쇠 격자 밖으로 열쇠가 튀어나오더라도 자물쇠의 구멍만 채워지면 열 수 있습니다.

 

풀이방법

N, M은 20 이하의 작은 수 입니다. 2차원 배열이기에 최대 사이즈는 400, 400 즉, 완전 탐색으로 풀라는 이야기로 해석할 수 있겠습니다. 그렇다면 모든 경우의 수를 하나하나 체크하는 방법으로 풀어야겠네요.

 

경우의 수는 아래와 같습니다.

1. 열쇠는 회전하여 자물쇠에 넣는것이 가능합니다. 3번의 회전이 가능하겠네요.

2. 칸을 이동해가면서 체크할 수 있겠습니다. 아래는 열쇠와 자물쇠 모두 2 * 2 크기일때의 경우의 수 입니다. 

 

위처럼 모든 위치에서 체크를 할 수 있겠습니다.

 

회전 하는 부분에서 어려움을 느낄수도 있을 것 같습니다.

0 0 0 0
0 1 1 0
1 0 0 0
0 0 1 1
-> 90도 회전
0 1 0 0
0 0 1 0
1 0 1 0
1 0 0 0

 

4*4배열을 회전할 때의 모습입니다.

2,0 위치에 있던 1은 0,1로

1,1 -> 1,2

1,2 -> 2,2

3,2 -> 2,0

3,3 -> 3,0

 

즉 규칙을 찾아보면 회전 후의 i = 회전 전의 j, 회전 후의 j = n -1 - 회전 전의 i입니다.

 

정답 코드

#include <string>
#include <vector>
#include <iostream>

using namespace std;

bool check(vector<vector<int>>& key, vector<vector<int>>& lock, int n, int y, int x)
{    
    for (int i = 0; i < lock.size(); i++)
        for (int j = 0; j < lock[i].size(); j++)
            if (lock[i][j] == key[i+n+y][j+n+x])
                return false;

    return true;
}

void Rotate(vector<vector<int>>& key)
{
    int n = key.size();
    vector<vector<int>> ret(n, vector<int>(n));
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j <n; j++)
            ret[i][j] = key[j][n-1-i];

    key = ret;
}



bool solution(vector<vector<int>> k, vector<vector<int>> lock) {
    
    int n = lock.size();
    int m = k.size();
    
    vector<vector<int>> key(n*3, vector<int>(n*3));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            key[i+n][j+n] = i >= m || j >= m ? 0 : k[i][j];
    
    for (int i = 0; i < 4; i++)
    {
        for (int i = -n+1; i < n; i++)
            for (int j = -n+1; j < n; j++)
                if (check(key, lock, n, i, j))
                    return true;

        Rotate(key);
    }
    
    return false;
}