1. 문제 해결
구현을 할 때, 주의해야 할 문장들이다.
1. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조
2. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다.
3. 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.필자는 해당 문제를 해결하기 위해 2단계로 나눠서 진행하였다.
1. 전처리 과정
2. 1번 과정을 통해 만들어진 큰 배열(bigLock)을 이용하여 (0,0)부터 (key.length-1,key.length-1)까지 탐색1-1. 전처리 과정
열쇠와 자물쇠를 이용하여 큰 배열(bigLock)을 생성을 한다.
bigLock을 만드는 이유는 열쇠가 자물쇠 밖에서도 움직이는 것을 표현하기 위해서이다.
열쇠의 길이가 M 이고 자물쇠의 길이가 N이기 때문에 큰 배열의 길이는 2 x M+N-2가 된다.
입출력 예시를 예로 들어 설명하면, 아래와 같은 그림이 된다. 
M=3, N=3이므로 2*3+3-2=7이 된다. 위와 같이 큰 배열을 생성한 후, 중앙에 자물쇠를 할당하면 된다.
파란색: 자물쇠, 빨간색: 열쇠
1-2. 탐색 시작
전처리 과정에서 만들어진 큰 배열(bigLock)을 이용하여 (0,0)부터 (key.length-1,key.length-1)까지 탐색을 진행한다.
시작 좌표를 기준으로 열쇠의 크기만큼 열쇠와 큰 배열(bigLock)을 순회하면서 4가지를 판단한다.
1. 큰 배열(bigLock)의 돌기와 열쇠의 돌기가 만나는 경우.
2. 큰 배열(bigLock)의 돌기와 열쇠의 홈이 만나는 경우.
3. 큰 배열(bigLock)의 홈과 열쇠의 홈이 만나는 경우.
4. 큰 배열(bigLock)의 홈과 열쇠의 돌기가 만나는 경우.4가지 경우의 수 중, 불가능한 것은 1번이다. 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다.
4번의 경우. (큰 배열(bigLock)의 홈에 열쇠의 돌기가 들어가는 경우)
큰 배열(bigLock)의 홈에 열쇠의 돌기를 할당한다. 그 후, 큰 배열의(bigLock)의 자물쇠 영역을 순회하면서 모든 홈이 열쇠의 돌기로 채워졌는지 판단한다.
2. 소스 코드
import java.util.*;
class Solution {
public static boolean solution(int[][] key, int[][] lock) {
int m = key.length;
int n = lock.length;
int bl = 2*m+n-2;
int[][] bigLock = new int[bl][bl];
copyArray(key.length,lock,bigLock); //중앙에 자물쇠 설치
for (int i = 0; i < 4; i++) {
if (move(key, lock,bigLock))
return true;
rotate90(key);
}
return false;
}
private static void rotate90(int[][] key) {
int[][] temp = new int[key.length][key.length];
for (int x = 0; x < key.length; x++) {
for (int y = 0; y < key.length; y++) {
int nx = y;
int ny = (key.length - 1) - x;
temp[nx][ny] = key[x][y];
}
}
copyArray(temp,key);
}
private static boolean move(int[][] key, int[][] lock, int [][] bigLock) {
for(int i =0 ; i<= bigLock.length - key.length ; i++) {
for(int j =0 ; j <= bigLock.length - key.length ; j++) {
if(check(i,j,bigLock,lock,key)) {
return true;
}
}
}
return false;
}
private static boolean check(int x, int y,int [][] bigLock, int [][] lock, int [][] key) {
int [][] temp = new int[bigLock.length][];
copyArray(bigLock,temp);
for(int i = x; i < x + key.length; i++) {
for(int j = y; j < y + key.length; j++) {
if(temp[i][j] != -1) {
if(temp[i][j] ==1 && key[i-x][j-y] == 1) //둘다 돌기인경우
return false;
else if(key[i-x][j-y] != 0)
temp[i][j] = key[i-x][j-y];
}
}
}
for(int i = key.length-1; i < key.length-1 + lock.length; i ++) {
for(int j = key.length-1 ; j < key.length-1 + lock.length ; j++) {
if(temp[i][j] == 0) //자물쇠에 홈이 존재하는 경우
return false;
}
}
return true;
}
private static void copyArray(int [][] src , int [][] dest) {
int idx = 0;
for(int[] s : src) {
dest[idx++] = Arrays.copyOf(s, s.length);
}
}
private static void copyArray(int kl,int [][] src , int [][] dest) {
for(int [] d : dest) {
Arrays.fill(d, -1);
}
for(int i =0 ; i < src.length ; i++) {
for(int j =0 ; j < src.length ; j++) {
dest[i+kl-1][j+kl-1] = src[i][j];
}
}
// print(dest);
}
private static void print(int [][] array) {
for(int i =0 ; i < array.length ; i++) {
for(int j =0 ; j < array.length ; j++) {
System.out.print(array[i][j]+ " ");
}
System.out.println();
}
}
}
Positive Thinking