プログラマ60059(ロックとキー)

📜 質問する

質問リンク
これは2次元配列実装+完全探索タイプの問題である.(ココア出力)

📖 に答える

私が初めて質問を見たとき、keyのすべてのcaseをlockに入れる方法が分からなかったので、私は長い時間をかけてこの解答を思い出しました.

上の図に示すように、[n + 2 * m - 2][n + 2 * m - 2]のサイズの配列を宣言し、key配列を迂回して鍵を使用してロックを開くことができるかどうかを決定すると、移動問題で提示されたkeyの場合、確認することができます.
次は回転キーの場合です.keyが時計回りに90度回転すると、1つのkeyに対して4種類のcaseが存在し、4種類のすべてのcaseに対して、上記の方法でkeyを移動し、鍵がロックされているかどうかを見て、すべてのcaseを決定することができます.

空間複雑度
1)(0,0) ~ (m + n - 2, m + n - 2)サイズのアレイx 2

最悪の場合、アレイのサイズは[n + 2 * m - 2][n + 2 * m - 2]なので、メモリオーバーフローの心配はありません.

時間の複雑さ
1)黒板にキー値を付け、すべてのcaseを確認するプロセス[58][58]

最悪の場合はkeyを4回回転させるのでO(m^4 * n^2)程度です.残りの過程を合わせても、約1秒で問題を解決することができます.

🖥 コード#コード#

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

using namespace std;

int board[60][60], board_temp[60][60];
int m,n;

//시계방향 90도 회전 구현
void rotate_arr(vector<vector<int>>& key) {
    int temp[60][60];
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            temp[x][m - 1 - y] = key[y][x];
    
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            key[y][x] = temp[y][x];
}

bool isPossible() {
    for(int y = m - 1; y < m + n - 1; y++)
        for(int x = m - 1; x < m + n - 1; x++)
            if(board_temp[y][x] != 1)
                return false;
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    m = key.size();
    n = lock.size();
    
    for(int y = m - 1; y < m + n - 1; y++)
        for(int x = m - 1; x < m + n - 1; x++)board[y][x] = lock[y - m + 1][x - m + 1];
        
    bool answer = false;
    for(int dir = 0; dir < 4; dir ++) {    
        rotate_arr(key);
        for(int y = 0; y < m + n - 1; y++){
            for(int x = 0; x < m + n - 1; x++){
                
                //board_temp 초기화!
                for(int y = 0; y < n + 2 * m - 2; y++)
                    for(int x = 0; x < n + 2 * m - 2; x++)
                        board_temp[y][x] = board[y][x];
                
                //board_temp에 key 값들을 더해봄
                for(int yy = y; yy < y + m; yy++){
                    for(int xx = x; xx < x + m; xx++){
                        board_temp[yy][xx] += key[yy - y][xx - x];        
                    }
                }
                /*
                cout << "-----------------------\n";
                for(int y = 0; y < n + 2 * m - 2; y++){
                    for(int x = 0; x < n + 2 * m - 2; x++){
                        cout << board_temp[y][x] << ' ';
                    }
                    cout << '\n';
                }
                */
                if(isPossible())return true;
            }
        }
    }
    return answer;
}

🔨 フィードバック

一つのプールを考えて実施したのですが、いくつか(?)実装エラーが発生しました.
プログラマでは、変数のデータ型は固定されています.通常、いくつかの変数をグローバル変数として宣言し、他の関数で使用する習慣があるので、疲れています.
回転4 * 6.4 * 10^7値の関数を実現するために、実際のキー値を直接回転させるには、key方式が用いられる.

void rotate_arr(vector<vector<int>>& key) {
    int temp[60][60];
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            temp[x][m - 1 - y] = key[y][x];
    
    for(int y = 0; y < m; y++)
        for(int x = 0; x < m; x++)
            key[y][x] = temp[y][x];
}

実際の関数から見ると,temp配列に回転値を一時的に格納し,キー値に再保存する方式である.1回目の実施では,想像以上に回転が難しいことを考慮して,問題に例3*3行列を描いて検証した.(理解しない場合は、簡単な例を直接手で開きます.)
⑤」という二次元配列の問題は、直接手で解くと確実にコードが実現しやすい!