프로그래머스(시뮬레이션, 카카오기출; 자물쇠와 열쇠) c++

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

using namespace std;

void debugMatrix(vector<vector<int>>& key)
{
    for(int i = 0; i < 3; ++i)
    {    
        for(int j = 0; j < 3; ++j)
            cout << key[i][j] << " ";
        cout << endl;
    }
    
}

vector<vector<int>> rotate90(vector<vector<int>>& key)
{
    int n = key.size();
    vector<vector<int>> rotated(n, vector<int>(n));
    for(int row = 0; row < n; ++row)
        for(int col = 0; col < n; ++col)
            rotated[col][n - 1 - row] = key[row][col];
    return rotated;
}

bool check(vector<vector<int>>& board, int lockSize, int keySize)
{
    // board 전체 크기 중, 가운데 lock 영역만 확인
    for(int i = keySize; i < keySize + lockSize; ++i)
        for(int j = keySize; j < keySize + lockSize; ++j)
            if(board[i][j] != 1) return false;
    return true;
}

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

    int lockSize = lock.size();
    int keySize = key.size();
    int boardSize = lockSize + keySize * 2;
    
    
    for(int rotation = 0; rotation < 4; ++rotation)
    {
        key = rotate90(key);        // 매번 90도씩 회전
        
        for(int x = 0; x < boardSize - keySize; ++x)
        {
            for(int y = 0; y < boardSize - keySize; ++y)
            {
                // 큰 board 준비, 가운데에 lock 배치
                vector<vector<int>> board(boardSize, vector<int>(boardSize, 0));
                for(int i = 0; i < lockSize; ++i)
                    for(int j = 0; j < lockSize; ++j)
                        board[i + keySize][j + keySize] = lock[i][j];
                
                // key를 (x, y) 위치에 더하기
                for (int i =0; i < keySize; ++i)
                    for(int j = 0; j <keySize; ++j)
                        board[x+i][y+j] += key[i][j];
                
                
                // lock 영역이 전부 1인지 확인
                if(check(board, lockSize, keySize)) return true;
            }
        }
    }
    
    return false;
}

 

해설:

key를 회전 시키고 lock에 맞춰야 하며 lock의 배열을 벗어나면 에러가 발생하기 때문에 boardSize = lockSize + keySize * 2로 크기를 늘려준다(board 중앙에 lock을 배치 후 key를 움직여야 하기 테두리*2라고 생각하면 편함)

이제 회전에 대해서는 

rotated[col][n - 1 - row] = key[row][col]; 으로 대입하는데 row = 0, col = 0이라고 대입했을때 이중for문으로 col이 먼저 증가 되기에 현재 row에 있는 값을 col -> [0 2], [1 2], [2 2]으로 옮기다고 생각하면 된다. 이렇게 4번 회전한다.

 

그리고 keysize만큼 lock을 가운데 배치. 그리고 x,y를 0에서부터 3까지 늘어나며 keysize가 3인 상태에서 board의 lefttop에서 rightbottom까지 점진적으로 전진하며 각과 위치를 늘려가면 0이 안나올때까지 돌려 봅니다.