(2018카카오) 자물쇠와 열쇠 Java

https://programmers.co.kr/learn/courses/30/lessons/60059

1. Lock의 약 3배크기의 그리드를 준비한다.
2. Lock을 그리드의 중앙으로 복사한다.
3. Key값을 각각의 Lock의 꼭짓점부터 순회한다.
4. 더불어 Key를 회전(rotate)시키면서 탐색한다.
5. 탐색할시에 Lock위치에 해당하는 인덱스의 값이 모두 1이어야 Lock이 딱 맞는걸로 판별된다.

그리드 예시1 https://www.youtube.com/watch?v=I1App3qLi6o

위의 그림처럼 키의값이 겹치면 1이 아닌것을 return하게 된다.

 

 

dfs방식 : boolean isOk값을 true냐 false냐로 판단한다.

public void dfs(int[][]key, int [][] lock, int cnt) {
​​​​​​​​check(key, lock, 0, 0);
​​​​​​​​if(isOk) return;
​​​​​​​​if(cnt >= 4) return;
​​​​​​​​int[][] temp = rotate(key);//키회전시킨걸로 탐색
​​​​​​​​dfs(temp, lock, cnt+1);//rotate ++;
​​​​}

위처럼, key값을 받고 lock에 대하여 check를 한다음, isOk가 true인 경우에는 더이상 탐색하지 않고 true반환.

cnt는 rotate(회전)을 하기 위해서 사용하는 변수다.

그리고 회전시킨key를 다시 dfs재귀호출한다.

 

• 회전

rotate는 이중for문을 이용한다. 

 

회전시 i값은 j값이되고 j값은 역배열된다.

​public int[][] rotate(int [][] key) { //회전
​​​​​​​​int len = key.length;
​​​​​​​​int[][] temp = new int[len][len];
​​​​​​​​for(int i=0; i<len; i++) {
​​​​​​​​​​​​for(int j=0; j<len; j++) {
​​​​​​​​​​​​​​​​temp[i][j] = key[len-j-1][i];
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return temp;
​​​​}

• check

public void check(int[][] key, int[][] lock, int x, int y) {
​​​​​​​​if(isOk) return;
​​​​​​​​if(y+key.length>lock.length) {//세로로 순환하고 가로값 증가하면서
​​​​​​​​​​​​y=0;//아래로가다가 다시 위로
​​​​​​​​​​​​x++;//오른쪽(x)으로 y++하면서 탐색
​​​​​​​​}
​​​​​​​​if(x+key.length>lock.length) return;//x값 다 돌았으면 종료.

​​​​​​​​int[][] copyLock = new int[lock.length][lock.length];
​​​​​​​​for(int i=0; i<lock.length; i++) {
​​​​​​​​​​​​copyLock[i] = lock[i].clone();
​​​​​​​​}
​​​​​​​​//탐색시작
​​​​​​​​boolean isFail = false;//실패냐?
​​​​​​​​loop:
​​​​​​​​for(int i=0; i<key.length; i++) {
​​​​​​​​​​​​for(int j=0; j<key.length; j++) {
​​​​​​​​​​​​​​​​if(key[i][j]==1) {//key가 1인 부분이
​​​​​​​​​​​​​​​​​​​​if(copyLock[i+x][j+y]==1) {//같이 1이면 실패
​​​​​​​​​​​​​​​​​​​​​​​​isFail = true;
​​​​​​​​​​​​​​​​​​​​​​​​break loop;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​​​​​copyLock[i+x][j+y] = key[i][j];
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(!isFail) {
​​​​​​​​​​​​loop:
​​​​​​​​​​​​for(int i=0; i<lock.length/3; i++) {
​​​​​​​​​​​​​​​​for(int j=0; j<lock.length/3; j++) {
​​​​​​​​​​​​​​​​​​​​if(copyLock[i+lock.length/3][j+lock.length/3] != 1) {
​​​​​​​​​​​​​​​​​​​​​​​​isFail = true;
​​​​​​​​​​​​​​​​​​​​​​​​break loop;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(!isFail) {
​​​​​​​​​​​​isOk = true;
​​​​​​​​​​​​return;
​​​​​​​​}
​​​​​​​​check(key, lock, x, y+1);//다음줄 y값 실행
​​​​}

재귀적으로 check를 호출하여 한 행씩 검사한다.

 

 

전체코드

class Solution {
​​​​static boolean isOk = false;

​​​​public boolean solution(int[][] key, int[][] lock) {
​​​​​​​​int len = lock.length;
​​​​​​​​//3배 확장 후 중앙으로 옮기기
​​​​​​​​int[][] copyLock = new int[len*3][len*3];
​​​​​​​​for(int i=0; i<len; i++) {
​​​​​​​​​​​​for(int j=0; j<len; j++) {
​​​​​​​​​​​​​​​​copyLock[i+len][j+len] = lock[i][j];
​​​​​​​​​​​​}
​​​​​​​​}

​​​​​​​​dfs(key, copyLock, 0);
​​​​​​​​return isOk;
​​​​}
​​​​public void dfs(int[][]key, int [][] lock, int cnt) {
​​​​​​​​check(key, lock, 0, 0);
​​​​​​​​if(isOk) return;
​​​​​​​​if(cnt >= 4) return;
​​​​​​​​int[][] temp = rotate(key);//키회전시킨걸로 탐색
​​​​​​​​dfs(temp, lock, cnt+1);//rotate ++;
​​​​}

​​​​public void check(int[][] key, int[][] lock, int x, int y) {
​​​​​​​​if(isOk) return;
​​​​​​​​if(y+key.length>lock.length) {
​​​​​​​​​​​​y=0;
​​​​​​​​​​​​x++;
​​​​​​​​}
​​​​​​​​if(x+key.length>lock.length) return;

​​​​​​​​int[][] copyLock = new int[lock.length][lock.length];
​​​​​​​​for(int i=0; i<lock.length; i++) {
​​​​​​​​​​​​copyLock[i] = lock[i].clone();
​​​​​​​​}

​​​​​​​​boolean isFail = false;
​​​​​​​​loop:
​​​​​​​​for(int i=0; i<key.length; i++) {
​​​​​​​​​​​​for(int j=0; j<key.length; j++) {
​​​​​​​​​​​​​​​​if(key[i][j]==1) {
​​​​​​​​​​​​​​​​​​​​if(copyLock[i+x][j+y]==1) {
​​​​​​​​​​​​​​​​​​​​​​​​isFail = true;
​​​​​​​​​​​​​​​​​​​​​​​​break loop;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​​​​​copyLock[i+x][j+y] = key[i][j];
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(!isFail) {
​​​​​​​​​​​​loop:
​​​​​​​​​​​​for(int i=0; i<lock.length/3; i++) {
​​​​​​​​​​​​​​​​for(int j=0; j<lock.length/3; j++) {
​​​​​​​​​​​​​​​​​​​​if(copyLock[i+lock.length/3][j+lock.length/3] != 1) {
​​​​​​​​​​​​​​​​​​​​​​​​isFail = true;
​​​​​​​​​​​​​​​​​​​​​​​​break loop;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​if(!isFail) {
​​​​​​​​​​​​isOk = true;
​​​​​​​​}
​​​​​​​​check(key, lock, x, y+1);
​​​​}

​​​​public int[][] rotate(int [][] key) { //회전
​​​​​​​​int len = key.length;
​​​​​​​​int[][] temp = new int[len][len];
​​​​​​​​for(int i=0; i<len; i++) {
​​​​​​​​​​​​for(int j=0; j<len; j++) {
​​​​​​​​​​​​​​​​temp[i][j] = key[len-j-1][i];
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return temp;
​​​​}
}