with code & food :: [프로그래머스] 자물쇠와 열쇠

[프로그래머스] 자물쇠와 열쇠 - 2020 카카오 공채 (완전탐색

카테고리 없음2020. 11. 12. 23:24

뷰어
댓글로
이전글
다음글

문제 내용

문제 설명

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 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가 lock안에서만 움직이는것도 아니고 어디서 끝을 맺어야 할지 모르므로 이 방법은 아니라고 느꼈습니다.

도저히 방법이 생각이 안 나 다른 분들의 풀이를 보았고 제가 잊지 않기 위해 다시 한전 정리할 겸 여러분들께 알려드립니다.

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

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

이 두 글을 보시면 key와 lock 사이즈가 M, N으로 서로 다른 정사각형임을 알 수 있습니다.

그리고 두 번째로 알 수 있는 사실은 사이즈입니다.

사이즈가 중요한 이유는 최대 사이즈가 완전 탐색 기법을 사용하였을 때 시간 안에 수행이 가능한 지를 보셔야 합니다.

최대 사이즈가 20 정도면 충분히 완전 탐색 기법을 사용해도 될 거 같습니다.

그렇다면 이것을 어떻게 서로 비교해 나갈까?입니다.

이것을 회전과, 상, 하, 좌, 우 이동을 한 번에 생각을 하면 머리가 아픕니다.

이것을 쪼개여 상, 하 좌, 우 이동과, 회전으로 나누어 생각해봅니다.

혹시 모눈종이라고 다들 아십니까?

모눈 종이 위에 특정 값을 적어 다른 종이에 비교하면 비치는 것처럼 이것도 이러한 방식을 이용하여 탐색해 보면 어떨까요

이런 방식으로 배열 자체를 이동하여 비교를 하는 것입니다.

이제 key 배열을 재배치하여 회전시켜 다시 위와 같이 비교해 나아가면 회전과 이동을 다 구현한 모습이 완성됩니다.

구현

위의 그림처럼 모눈종이 방법처럼 비교해 나아가려면 lock의 배열 사이즈를 크게 만들어줘야 할 거 같습니다.

key의 배열은 lock 밖에서도 비교하고 있기 때문입니다.

그럼 얼마큼 lock의 사이즈를 늘려주면 될까?

위 그림을 보시면 처음 비교를 시작하는 모습입니다.

배열의 길이가 기존 lock 배열 길이에서 key 배열 길이 - 1만큼 더 앞으로 생겼습니다.

또한 이 길이는 반대쪽까지 비교해야 하니 반대쪽도 key 배열 길이 - 1만큼 더 추가해 줘야 합니다.

**board = lock의 길이 + ( key의 길이 - 1 ) * 2**

이제 어느 정도 배열을 만들어야 하는지 알았으니 만들어보겠습니다.

void make_board(vector<vector<int>> &board, const vector<vector<int>> lock, const int key_size)
{
    const int board_size = board.size();

    for (int i = key_size - 1; i <= board_size - key_size; ++i)
    {
        for (int j = key_size - 1; j <= board_size - key_size; ++j)
            board[i][j] = lock[i - key_size + 1][j - key_size + 1];
    }
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
    int answer = false;
    const int lock_size = lock.size();
    const int key_size = key.size();
    
    const int board_size = lock_size + (key_size - 1) * 2;
    vector<vector<int>> board(board_size, vector<int>(board_size, 0));

    make_board(board, lock, key_size);

    ...
}

위 내용을 지나면 아래와 같은 큰 보드 판이 만들어집니다.(문제 예시로 예를 들겠습니다.)

0	0	0
0	0	0
1	1	1
1	1	0
1	0	1
0	0	0
0	0	0

외와 같은 그림을 이제 회전과 이동을 하면서 비교하면 이번 문제는 해결될 거 같습니다.

비교 방식은 회전한 key배열을 모든 이동에 비교해 본 후 풀리나 안 풀리나 확인하는 방식입니다.

즉, 회전을 담당하는 반복분 안에 이동을 담당하는 반복문이 있는 그림입니다.

그리고 회전은 90도 회전 기준으로 총 360도가 한 바퀴이니 4번만 돌려주면 모든 방향으로 탐색이 가능합니다.

bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
    ...
    
    int rotate = 0;
    while (rotate < 4)
    {

        for (int i = 0; i < board_size - key_size; ++i)
        {
            for (int j = 0; j < board_size - key_size; ++j)
            {
                if (insert_key(i, j, board, key))
                {
                    answer = true;
                    return answer;
                }
            }
        }

        rotate_key(key);
        ++rotate;
    }
    return answer;
}

위 그림에서 각 시작 값을 insert_key에 넣어 비교하는 중입니다.

여기서 key와 lock은 1이나 0이 저장되었습니다.

그리고 key값과 lock값이 더 해졌을 때 2가 나오면 키와 lock의 위치가 겹친다는 뜻입니다.

또한 0일 경우에는 lock에 값이 정상적으로 들어가지 않아 풀리지 않은 것입니다.

즉, lock의 모든 값이 1로 통일돼야 정상적으로 key의 값이 lock에 들어갔다 할 수 있습니다.

bool insert_key(const int start_y, const int start_x,
                vector<vector<int>> board, vector<vector<int>> key)
{
    const int board_size = board.size();
    const int key_size = key.size();

    for (int i = start_y; i < start_y + key_size; ++i)
    {
        for (int j = start_x; j < start_x + key_size; ++j)
            board[i][j] += key[i - start_y][j - start_x];
    }

    // show_board(board);

    for (int i = key_size - 1; i <= board_size - key_size; ++i)
    {
        for (int j = key_size - 1; j <= board_size - key_size; ++j)
        {
            const int value = board[i][j];
            if (value == 0 || value > 1)
                return false;
        }
    }
    return true;
}

주석으로 달아놓은 show_board() 함수는 테스트 코드에 같이 첨부하겠습니다.

show_board() 함수는 board의 변화를 확인할 수 있는 코드입니다.

마지막으로 회전하는 것을 담당하는 rotate_key() 함수입니다.

이 함수는 90도씩 회전하는 함수입니다.

(매개변수로 받을 때 그 안의 값이 변경될 시 '&' 참조자를 사용하여 계산하는 것이 속도면에서도 빠릅니다.)

void rotate_key(vector<vector<int>> &key)
{
    const int key_size = key.size();

    vector<vector<int>> key_tmp(key_size, vector<int>(key_size, 0));

    for (int i = key_size - 1; i >= 0; --i)
    {
        for (int j = 0; j < key_size; ++j)
        {
            key_tmp[i][j] = key[key_size - j - 1][i];
        }
    }

    key = key_tmp;
}

전체 코드

#include <iostream>
#include <vector>

using namespace std;

void rotate_key(vector<vector<int>> &key)
{
    const int key_size = key.size();

    vector<vector<int>> key_tmp(key_size, vector<int>(key_size, 0));

    for (int i = key_size - 1; i >= 0; --i)
    {
        for (int j = 0; j < key_size; ++j)
        {
            key_tmp[i][j] = key[key_size - j - 1][i];
        }
    }

    key = key_tmp;
}

void make_board(vector<vector<int>> &board, const vector<vector<int>> lock, const int key_size)
{
    const int board_size = board.size();

    for (int i = key_size - 1; i <= board_size - key_size; ++i)
    {
        for (int j = key_size - 1; j <= board_size - key_size; ++j)
            board[i][j] = lock[i - key_size + 1][j - key_size + 1];
    }
}

bool insert_key(const int start_y, const int start_x,
                vector<vector<int>> board, vector<vector<int>> key)
{
    const int board_size = board.size();
    const int key_size = key.size();

    for (int i = start_y; i < start_y + key_size; ++i)
    {
        for (int j = start_x; j < start_x + key_size; ++j)
            board[i][j] += key[i - start_y][j - start_x];
    }

    // show_board(board);

    for (int i = key_size - 1; i <= board_size - key_size; ++i)
    {
        for (int j = key_size - 1; j <= board_size - key_size; ++j)
        {
            const int value = board[i][j];
            if (value == 0 || value > 1)
                return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock)
{
    int answer = false;
    const int lock_size = lock.size();
    const int key_size = key.size();
    const int board_size = lock_size + (key_size - 1) * 2;

    vector<vector<int>> board(board_size, vector<int>(board_size, 0));

    make_board(board, lock, key_size);

    int rotate = 0;
    while (rotate < 4)
    {

        for (int i = 0; i < board_size - key_size; ++i)
        {
            for (int j = 0; j < board_size - key_size; ++j)
            {
                if (insert_key(i, j, board, key))
                {
                    answer = true;
                    return answer;
                }
            }
        }

        rotate_key(key);
        ++rotate;
    }
    return answer;
}

테스트 코드 (필요하신 분만)

int main()
{

    const vector<vector<vector<int>>> key_testcases{
        {{0, 0, 0},
         {1, 0, 0},
         {0, 1, 1}}};

    const vector<vector<vector<int>>> lock_testcases{
        {{1, 1, 1},
         {1, 1, 0},
         {1, 0, 1}}};

    for (int i = 0; i < key_testcases.size(); ++i)
    {
        const int ret = solution(key_testcases[i], lock_testcases[i]);
        cout << ret << endl;
    }
    return 0;
}

아래는 보드를 확인해주는 함수입니다.

void show_board(vector<vector<int>> board)
{
    const int board_size = board.size();

    for (int i = 0; i < board_size; ++i)
    {
        for (int j = 0; j < board_size; ++j)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

끝맺음

이번 문제는 저도 상당히 생각을 해보았지만 스스로 풀지는 못하였던 문제입니다.

다시 한번 함수 별로 정리를 하면서 각각이 어떤 의미를 하는지 또한 어떻게 푸는지 알 수 있습니다.

이 문제는 풀이를 보더라도 배열을 구성하는 방법이 수식으로 되어있어 다소 직관적이지 않을 수 있으나 조금만 손으로 적어보시면 금방 깨달으실 수 있을 거라 생각합니다..

저 또한 이해가 안 갈 때마다 종이를 꺼내어 항상 그려보곤 합니다. 하하...

저작자표시

with code & food