[프로그래머스 lv3] 자물쇠와 열쇠

해설

key를 회전해서 lock의 특정 위치에 꽂을 때 lock의 모든 홈이 채워지는지 확인하는 문제이다.

문제를 처음 본 순간 확인해야 하는 것은 m과 n의 범위이다.

m과 n의 범위가 크지 않으므로 key를 회전시키고 특정 위치에 꽂는 모든 경우를 확인할 수 있겠다는 생각이 든다.

 

모든 경우를 확인하기 위한 단계를 다음과 같다.

 

1) 먼저, key를 90도로 4번 회전시킨다. 

 

2) key를 회전시킨 각각의 경우에 대하여 lock 위에 key를 꽂을 수 있는 모든 위치를 탐색한다. key의 한변의 길이를 m, lock의 한변의 길이를 n이라 할 때, 키가 포개지는 시작점은 (m-1, m-1) 부터 (n-1+m-1, n-1, m-1) 까지 가능하다. 해당 위치를 시작점으로 키를 포갰을 때 n x n의 lock에 들어올 수 있는 구역을 찾아 tmp에 기록해 놓는다. 

 

3) 키가 포개진 영역에 대한 정보 tmp와 lock을 비교한다. lock을 기준으로, 홈은 돌기와 포개져야 하고 돌기는 홈과 포개져야 한다. 따라서, lock[i][j]와 tmp[i][j]가 같으면 자물쇠는 열리지 않으므로 false를 리턴한다. 모든 영역에 대해 lock[i][j]과 tmp[i][j]가 다르면 true를 리턴한다. 

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int m, n;

void rotate(vector<vector<int>>& key) {
    
    vector<vector<int>> tmp(m, vector<int>(m, 0));
    
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++)
            tmp[i][j] = key[m-1-j][i];
    }
    
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) 
            key[i][j] = tmp[i][j];
    }
}

bool OOB(int x, int y) {
    return x < 0 || x >= n || y < 0 || y >= n;
}

void checkKeyArea(vector<vector<int>>& tmp, const vector<vector<int>>& key, int stx, int sty) {
    
    for (int i=0; i<m; i++) {
        for (int j=0; j<m; j++) {
            int nx = i+stx;
            int ny = j+sty;
            if (OOB(nx, ny)) continue;
            tmp[nx][ny] = key[i][j];
        }
    }
}

bool compare(const vector<vector<int>>& tmp, const vector<vector<int>> lock) {
    
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if (tmp[i][j] == lock[i][j]) return false;
        }
    }
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    
    m = (int)key.size();
    n = (int)lock.size();
    
    for (int i=0; i<4; i++) {
        if (i != 0) rotate(key);
        
        for (int stx=-(m-1); stx<=(n-1+m-1); stx++) {
            for (int sty=-(m-1); sty<=(n-1+m-1); sty++) {
                vector<vector<int>> tmp(n, vector<int>(n, 0));
                checkKeyArea(tmp, key, stx, sty);
                if (compare(tmp, lock)) return true;

            }
        }
    }
    return false;
}