자물쇠와 열쇠
문제 해석
자물쇠와 열쇠 배열이 주어졌을 때, 자물쇠가 알맞게 채워질 수 있는지 여부를 판단하는 문제입니다.
자물쇠는 홈, 열쇠는 홈과 돌기로 구성되어있고 열쇠는 회전과 이동이 가능합니다.
열쇠의 돌기부분은 자물쇠의 홈부분에 딱 맞게 채우면 됩니다.
자물쇠 영역 외의 범위는 정답의 영향을 주지 않습니다.
자물쇠 영역 내는 다음과 같은 조건을 만족해야합니다.
- 열쇠의 돌기와 자물쇠의 홈이 정확히 일치해야합니다.
- 열쇠의 돌기와 자물쇠의 돌기가 겹치면 안됩니다.
- 자물쇠의 모든 홈이 채워져야 합니다.
설계(10)
열쇠를 회전과 이동을 시켜가면서 자물쇠가 완전히 채워지는지 확인하면 되는 문제입니다.
인덱스 범위 초과를 방지하기 위하여 arr배열에 20을 offset한 자물쇠 배열의 값들을 저장해 놓습니다.
그러면 최대 2xM+N길이의 배열을 검사하는 셈이 되므로 O(2xM+N)xO(2xM+N)xO(4)로 모두 탐색이 가능합니다.
copy_arr에 기존 arr를 복사한 후 key값을 더하는 식으로 배열을 완성시킨 후, 자물쇠의 홈이 모두 채워졌는지 검사하면 됩니다.
구현(15)
코드
#include <iostream>
#include <string>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 61
int arr[MAXN][MAXN];
int copy_arr[MAXN][MAXN];
bool simulate(int sx, int sy,vector<vector<int>> key){
int M = key.size();
for (int i = 0; i < M; i++){
for (int j = 0; j < M; j++){
if (key[i][j] && copy_arr[i+sx][j+sy]) return false;
copy_arr[i+sx][j+sy] += key[i][j];
}
}
return true;
}
bool check(vector<vector<int>> lock){
int N = lock.size();
for (int i = 0; i < N; i++){
for (int j = 0 ;j < N; j++){
if (!copy_arr[i+20][j+20]) return false;
}
}
return true;
}
void rotate(vector<vector<int>> &key){
vector<vector<int>> copy_key = key;
int M = key.size();
for (int i = 0 ; i < M; i++){
for (int j = 0 ;j < M; j++){
key[j][M-1-i] = copy_key[i][j];
}
}
}
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
int N = lock.size();
int M = key.size();
for (int i = 0 ; i< N; i++){
for (int j = 0 ;j < N; j++){
arr[i+20][j+20] = lock[i][j];
}
}
for (int i = 0; i < 4; i++){
if (i) rotate(key);
for (int offset_x = 19-M; offset_x <= 20+N; offset_x++){
for (int offset_y = 19-M; offset_y <=20+N; offset_y++){
memcpy(copy_arr,arr,sizeof(arr));
if (simulate(offset_x,offset_y,key) == true && check(lock)==true) return true;
}
}
}
return false;
}
디버깅
제출결과
마무리
인덱스 초과까지 생각했으면 구현이 쉽지않았을 것 같았습니다. 이를 방지하기 위하여 메모리를 조금 낭비하더라도 적절히 큰 배열을 사용하였습니다.