[프로그래머스]2020 KAKAO BLIND RECRUITMENT : 자물쇠와 열쇠 (level 3)(c++)

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

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

 

회전과 이동 구현

#include <string>
#include <vector>

using namespace std;

int N, M, K;

void rotate(vector<vector<int>> &key)
{
    // 임시 벡터를 활용하여 원본 벡터를 회전시킨다
    vector<vector<int>> tmp(M, vector<int>(M));
    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            tmp[i][j] = key[i][j];
        }
    }

    for (int i = 0; i < M; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            key[j][M - 1 - i] = tmp[i][j];
        }
    }
}

bool check(vector<vector<int>> &board, vector<vector<int>> &key, int a, int b)
{
    // board 중앙에 놓여진 자물쇠의 영역의 격자들을 확인한다
    for (int i = M; i < N + M; ++i)
    {
        for (int j = M; j < N + M; ++j)
        {
            int ok = 0;

            // key가 자물쇠 영역에 없다면 자물쇠의 격자값만 확인
            if (i - a < 0 || i - a >= M || j - b < 0 || j - b >= M)
            {
                ok = board[i][j];
            }
            // key가 자물쇠의 영역에 있다면 같은 칸에 위치한 두 값을 확인
            else 
            {
                ok = board[i][j] + key[i - a][j - b];
            }
            
            // 결과가 1이 아니면 실패
            if (ok != 1)
            {
                return false;
            }
        }
    }
    // 자물쇠 모든 격자의 값이 1이 되면 성공
    return true;
}

bool unlock(vector<vector<int>>& board, vector<vector<int>>& key)
{
    /*
        key벡터를 90`씩 총 4번 회전시키고 (0` 포함)
        board에서 이동시킨다
    */
    for (int ltt = 0; ltt < 4; ++ltt)
    {
        for (int i = 0; i <= K - M; ++i)
        {
            for (int j = 0; j <= K - M; ++j)
            {
                /*
                    key[0][0]가 board[i][j]위치로 이동했을 때
                    자물쇠의 모든 홈이 채워지는지 확인
                */
                if (check(board, key, i, j))
                {
                    return true;
                }
            }
        }

        // key 벡터를 90`만큼 회전
        rotate(key);
    }

    return false;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {

    /*
        ------------------
        |    --------    |
        |    | lock |    | 
        |    --------    |
        ------------------
        위와 같은 형태로 lock이 중앙에 들어가도록
        한변 길이 N + 2 * M의 2차배열을 만든다.
    */
    M = key.size();
    N = lock.size();
    K = N + 2 * M;
    
    vector<vector<int>> board(K, vector<int>(K));
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            board[i + M][j + M] = lock[i][j];
        }
    }

    // 주어진 키로 자물쇠를 해제할 수 있으면 true반환
    return unlock(board, key);
}

 

 

문제에서 상당히 많은 힌트를 주고 있는 문제이다.

 

열쇠는 회전과 이동이 가능하며
열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다.

열쇠를 회전하고 이동시키라는 뜻이다.

 

자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 
자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 
열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 
또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

자물쇠를 가운데 두고 열쇠를 이리저리 이동시키는데,

자물쇠 영역만 확인하면 된다는 뜻이다.

 

key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.

숫자 제한이 매우 작다. Brute Force로 가능하다는 뜻이다.

 

 

다른 문제에 비해 코드 볼륨이 조금 크다.

그리고 완전탐색으로 풀라고 문제에서 티를 팍팍 내고 있다.

따라서 효율성을 추구하기보다는, 버그를 최대한 덜 내는데에 집중해서 코드를 짜는게 좋다.

 

 

기본 아이디어는 다음과 같다.

1. 위 그림처럼 커다란 보드를 만들어서 중앙에 자물쇠를 놓고 key를 이동시킨다

2. 보드 전체를 이동했는데 맞는 key 위치가 없으면 key를 90˚ 회전시킨다.

 

자물쇠가 맞춰졌는지 확인 할 때에는, 자물쇠 영역 안에 있는 key값을 더해주면 된다.

int ok = 0;

// key가 자물쇠 영역에 없다면 자물쇠의 격자값만 확인
if (i - a < 0 || i - a >= M || j - b < 0 || j - b >= M)
{
    ok = board[i][j];
}
// key가 자물쇠의 영역에 있다면 같은 칸에 위치한 두 값을 확인
else 
{
    ok = board[i][j] + key[i - a][j - b];
}

// 결과가 1이 아니면 실패
if (ok != 1)
{
    return false;
}

 

 

기타 세부사항은 코드를 참고하는 것이 더 직관적일듯 하다.