- 크기가 20이기 때문에 완전탐색을 해도 괜찮다.
- lock이 n, key가 m 임
- 200 x 200 x 4 가지 경우가 나올 거임. ( 각 key를 한 칸씩 이동시켜나가며 convolve시켜나간다고 생각하면 n x n x 4가지 경우가 나올 것이기 때문임)
- 그런데 n은 최대 20이기때문에 완전탐색을 해도 괜찮다.
- n,m은 최대 20이기 때문에 메모리 상으로도 괜찮다.
- 4가지의 열쇠를 모두 만들어서 해도 괜찮다.
- 자물쇠 : NxN 정사각형, 홈(0), 돌기(10)
- 열쇠 /; Mx M. 정사각형 —> 회전, 이동 가능. —>”자물쇠의 홈!(0)”에 “열쇠의 돌기(1)”가 딱 맞아야 한다.
- “열쇠의 돌기” 가 “자물쇠의 돌기” 와 만나면 X !!!
- “ 자물쇠의 모든 홈”을 채워 “비워있는 곳이 없어야 “ 한다.
- “자물쇠 영역을 벗어난 부분에” 있는 “열쇠의 홈, 돌기”는 자물쇠를 여는데에는 영향을 주지 않으나, “열쇠의 돌기”가 “자물쇠의 돌기”와 만나선 안 된다.
-
회전
-
int[][][] gkey = new int[m][m][4];
-
여기에 0도,90,180도,270도의 key모양을 저장한다.
-
Rotation 구현은 다음과 같이 할 수 있다.
- 이 방법은, 별개의 메모리를 사용한다는 단점이 있었는데, 어차피 이 문제는, 각각의 모양을 저장 해 두고 풀어야 하기 때문에 괜찮다고 생각되었다.
-
-
Convolve
-
초반에 생각했던 것
-
Padding을 넣어주는게 훨씬 편한 방법이었다.
-
1이 돌기임. 0이 홈이고
-
자물쇠의 0에 열쇠의 1이 들어가야하고 —> 1
-
자물쇠의 1에 열쇠의 0 이 들어가야함. —> 1 ..
-
자물쇠의 0에 열쇠의 0 이 있거나, 자물쇠의 1에 열쇠의 1이 있음 안됨
-
이런 경우에는 XOR이지
- 0 ,1 —> 1
- 1, 0 —> 1
- 1, 1 —> 0
- 0 ,0 —> 0
- 즉, 0이 나오면 안 됨 . —> 0 이 한 개라도 존재한다면, false임. 그게 아니면 true를 반환한다. —> 이 덕분에 lock의 모든 원소가 1인 경우에도 true가 리턴되었다.
-
Convolution 구현을 어떻게 할까??? —> 아예 커다란 2D 배열을 하나 할당해서 푸는게 더 낫다.
- 크기 : 2M + n-2 이다.
- 중간에 lock을 배치 한다 —> row : m-1 ~ m+n-2 까지 , col역시 같음.
- key와 convolution 할 때 마다, 중앙의 lock 을 초기화 시켜줘야 한다.
-
-
아래코드를 작성함 —> Runtime Error가 나왔는데 아주 사소한 이유였다.. 이유는..아래에
package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class main {
public static int n,m;
public static int[][] glock;
public static int[][][] gkey;
public static void setKey(){
// 90도씩 회전시켜
// i 번째 도형을 회전시켜 저장한다.
/*
* row --> col.lengt() - row 로 변환된다.
* 어차피 각자의 memory를 이미 차지하고 있기 때문에.
* */
for(int i=0;i<3;i++){
for(int r =0;r<m;r++){
for(int c=0;c<m;c++){
gkey[i+1][c][m-1-r] = gkey[i][r][c];
}
}
}
}
public static boolean solution(int[][] key, int[][] lock) {
boolean answer = false;
n = lock.length;
m = key.length;
glock = lock;
// key를 ......
gkey = new int[4][m][m];
// 첫 번째 모양을 세팅
for(int r=0;r<lock.length;r++){
for(int c =0;c<lock[0].length;c++){
gkey[0][r][c]= key[r][c];
}
}
setKey();
answer = convolve();
return answer;
}
public static boolean convolve(){
int len = 2*m+n-2; // 7
int[][] sheet = new int[len][len];
int row = m-1, col = m-1;
for(int key=0;key<4;key++) {
// 맨 왼쪽 맨 위부터 key를 연산시킨다.전체를 XOR 연산 시키더라도, 마지막에는 중앙의 것만 확인하면 된다.
for (int r = 0; r <= len-m; r++) {
for (int c = 0; c <= len-m; c++) {
// 시트를 초기화 =====
// 중앙에 key를 재배치한다.(그 바깥은 상관 없다 ) --> 출력해 보니, 초기화는 잘된 거 맞음.
for(int lr=0;lr<n;lr++){
for(int lc=0;lc<n;lc++){
sheet[row+lr][col+lc]=glock[lr][lc];
}
}
// 매 번 (r,c)를 key 의 왼쪽 맨 위 꼭지점이라고 생각을 한다.
for(int kr=0;kr<m;kr++){
for(int kc=0;kc<m;kc++){
sheet[r+kr][c+kc] =(sheet[r+kr][c+kc] ^ gkey[key][kr][kc]);
}
}
// 해당 convolution 결과, 중앙의 key에 0 이 없다면 --> 성공이다
if(isLockOpen(sheet)) return true;
}
}
}
return false;
}
public static boolean isLockOpen(int[][] sheet){
int row = m-1, col = m-1;
// 중앙값만을 확인한다.
for(int lr=0;lr<n;lr++){
for(int lc=0;lc<n;lc++){
if(sheet[row+lr][col+lc]==0) return false;
}
}
return true;
}
public static void main(String[] args) throws IOException {
//Setting();
//boolean res = solution(new int[][]{{0, 0, 0}, {1, 0, 0}, {0, 1, 1}}, new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}});
//boolean res = solution(new int[][]{{0, 0, 0}, {1, 0, 0}, {0, 1, 1}}, new int[][]{{1, 1, 1}, {1, 1, 1}, {1, 1, 1}});
boolean res = solution(new int[][]{{1}}, new int[][]{{0}});
System.out.println(res);
}
}런타임 에러가 나왔었다.
혹시나 해서...
// 첫 번째 모양을 세팅
for(int r=0;r<lock.length;r++){
for(int c =0;c<lock[0].length;c++){
gkey[0][r][c]= key[r][c];
}
}기존의 윗 부분을 아래와 같이 변경하니 정답이 나왔다.
// 첫 번째 모양을 세팅
for(int r=0;r<m;r++){
for(int c =0;c<m;c++){
gkey[0][r][c]= key[r][c];
}
}