(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;
    }
}