[解析アルゴリズムプール]プログラマロックとキー(2020 KaKao Blind Recruition)

今日の2番目の問題はプログラマロックとキーです.同じく2020年のKACA公募問題であり、Level 3のシミュレーション問題である.

プログラマロックとキー

考古学者の「救命圏」は古代遺跡で秘密の扉を発見し、宝物や遺跡がたくさんあると推測した.ドアを開けてみると、ドアが特殊な形の鍵でロックされていて、ドアの前に紙があり、特殊な形の鍵でロックを解除する方法が書かれています.
ロックされたロックは、メッシュサイズが1 x 1のN x Nサイズの正方形メッシュであり、特殊な形状のキーはM x Mサイズの正方形メッシュである.
鍵には溝があり、鍵にも溝と突起があります.鍵は回転と移動が可能な構造で、鍵の回転部分が鍵の溝部分とぴったり合っていると鍵が開きます.ロック領域以外の鍵の溝と突起はロック解除に影響しないが、ロック領域内では鍵の突起とロックの溝が完全に一致し、鍵の突起とロックの突起にぶつかることができない必要がある.また、ロックのすべての溝を埋めなければなりません.そうすれば、ロックを解除できます.
パラメータにキーを表す2 D配列キーとロックを表す2 D配列ロックが与えられた場合、true(キーがロックを解除できる場合)とfalse(ロックを解除できない場合)を返すソルバを完了します.

にゅうしゅつりょく

結合はMxM(3≦M≦20,Mは自然数)サイズの二次元配列である.

ロックは、NxN(3≦N≦20、Nは自然数)サイズの2次元配列である.

Mは常にNより小さい.

キーとlockの要素は0または1で構成されます.

0は「主」部分、1は「回転」部分を表します.

keylockresult[[0, 0, 0], [1, 0, 0], [0, 1, 1]][[1, 1, 1], [1, 1, 0], [1, 0, 1]]true

私の答え

問題の正式な解答を読む前に、私は方法を考えました.
最も基本的な方法は、鍵をロック基準に回し、鍵を移動し、すべての状況を対象に確認が可能かどうか、タイムアウトが発生する可能性があるので、範囲を狭めて最小限の状況だけを考慮して確認する方法があります.
しかし問題で提案した鍵と鍵の大きさは最大20*20の2次元配列であるため,基本的な方法で解くことができるので選択した.
また,問題は特別なアルゴリズムを考え出すのではなく,少し難易度のあるシミュレーション問題であると考えたため,すべての鍵を4方向に向けて移動する方法を選択して確認した.
一番難しい部分は鍵を回すルールを見つけることです.
前回BOJ 15685竜曲線問題を解いた時も経験したが,配列移動や回転時の座標変化の規則性を探すには弱いようだ.
この部分では、問題リストの文章の助けでルールが見つかり、3*3の配列を基準に、9つの座標をすべてリストするときに、鍵を回し、(y1,x1) -> (y2, x2)を変換するときに、y2 = x1, x2 = N-1-y1のルールがあります.
2番目の投資時間の部分は、鍵をロック基準に移動したときに、ロック座標が鍵の座標にどのように変換されるかです.ロックの(i,j)を確認する場合、このとき鍵位置基準の変化量がdy, dx (-N+1 ~ M+1)であることを先に確認し、このときM*Mサイズの鍵アレイ内座標は(i + dy, j + dx)に変換される.
また、問題内容で鍵の回転や鍵の回転に遭遇してはいけないので、取り扱いにも注意!

コード#コード#

#include <iostream>
#include <vector>

using namespace std;

int N, M;

// key 회전 시키기
void rotateKey(vector<vector<int>> & key){
    vector<vector<int>> newKey(M, vector<int>(M, 0));

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

    key = newKey;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    int rotation = 0;
    N = lock.size();
    M = key.size();

    // 자물쇠의 홀 갯수 count
    int hole = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (lock[i][j] == 0) hole++;
        }
    }

    while (rotation < 4){
        if (rotation > 0) rotateKey(key);  // 3 번 열쇠 돌리기 

        for (int dy = M-1; dy >= -N+1 ; --dy) {
            for (int dx = M-1; dx >= -N+1 ; --dx) {
                // dy, dx = 열쇠와 자물쇠가 겹치도록 열쇠를 이동시킬 때 좌표 변화량 
                int count = 0;
                bool fail = false;
                for (int i = 0; i < N; ++i) {
                    for (int j = 0; j < N; ++j) {
                        // 자물쇠의 i, j 좌표와 겹치는 열쇠 좌표 구하기 
                        int keyY = i + dy, keyX = j + dx;
                        if (keyY>=0 && keyY<M && keyX>=0 && keyX<M && key[keyY][keyX] == 1) { // 열쇠의 돌기 부분 
                            if (lock[i][j] == 0) count++;  // 채워지는 부분 count 
                            else {  // 열쇠 돌기, 지물쇠의 돌기가 만날 수 없게 
                                fail = true;
                                i = N;
                                j = N;
                            }
                        }
                    }
                }
                if (!fail && count==hole) return true;
            }
        }
        rotation++;
    }

    return false;
}