자물쇠와 열쇠

문제

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

풀이

열쇠 배열을 한 번 90도로 회전할 때마다
슬라이딩 윈도우 기법을 사용하여
자물쇠에 열쇠가 들어갈 수 있는 모든 경우의 수를 확인한다.

슬라이딩 윈도우 기법?

위의 gif와 같이 5x5 배열을 3x3의 윈도우로 겹쳐가면서 확인하는 기법이다. (배열과 윈도우의 크기를 달라질 수 있음)

슬라이딩 윈도우 기법이 오른쪽 아래로 진행된다는 점이 중요하다.

1. 주어진 자물쇠 배열이 NxN이라면
   (Nx3)x(Nx3) 배열을 새로 놓아 가운데에 자물쇠 배열을 배치한다.

2. 자물쇠의 열쇠 구멍의 개수를 확인하고
   열쇠 배열을 슬라이딩 윈도우 기법으로
   열쇠 구멍과 열쇠가 맞을 때마다 열쇠 구멍의 개수를 줄인다.

3. 하지만 만약 자물쇠의 돌기와 열쇠의 돌기가 겹친다면 바로 맞지 않은 열쇠라는 것

코드

public class LockAndKey {
    public boolean solution(int[][] key, int[][] lock) {
        int N = lock.length; //자물쇠의 크기
        int[][] map = new int[N * 3][N * 3]; //자물쇠를 가운데에 넣는 큰 map 배열 생성
        int hole = 0; //열쇠 구멍의 개수

        for (int i = 0; i < N; i++) {
            System.arraycopy(lock[i], 0, map[N + i], N, N); //map배열 가운데에 넣는 copy 함수
            for (int j = 0; j < N; j++) {
                if (lock[i][j] == 0)
                    hole++;
            }
            //열쇠 구멍을 찾는 과정
        }

        for (int i = 0; i < 4; i++) {
            //슬라이딩 윈도우 기법 사용
            if (slidingWindow(key, map, N, hole)) {
                return true;
            }
            key = rotate(key); //만약 해결이 되지 않으면 키 90도 회전하기
        }
        return false;
    }

    private boolean slidingWindow(int[][] key, int[][] map, int N, int h) {
        int M = key.length; //열쇠의 크기
        int count = N + N;
        //처음에 N+N-1으로 해서 틀렸다..
        //0,0에서 시작해서 자물쇠가 끝나는 인덱스까지 확인해야 하기에 N+N

        for (int i = 0; i < count; i++) {
            //윈도우가 아래로 내려가는 반복문
            for (int j = 0; j < count; j++) {
                //윈도우가 오른쪽으로 옮겨가는 반복문
                if (unlock(key, map, M, i, j, N, h)) {
                    return true;
                    //잠금이 해제되면 true
                }
            }
        }
        return false;
    }

    private static boolean unlock(int[][] key, int[][] map, int M, int startX, int startY, int N, int hole) {
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                //i,j는 key 배열 안에서의 인덱스
                int mapX = startX + j;
                int mapY = startY + i;
                //startX, startY는 열쇠가 시작하는 곳으로 , 즉 열쇠 값을 다 확인하기
                if (mapX >= N && mapX < 2 * N && mapY >= N && mapY < 2 * N) {
                    //근데! 열쇠 중에서도 자물쇠 영역 안에 있는 열쇠들만 확인
                    if (map[mapY][mapX] == 1 && key[i][j] == 1) {
                        //자물쇠와 열쇠 둘 다 1이면 돌기이므로 아예 false
                        return false;
                    }
                    if (map[mapY][mapX] == 0 && key[i][j] == 1) {
                        //자물쇠가 0이고, 열쇠가 1이면 홈에 맞는다는 의미이므로 열쇠 구멍의 개수를 줄여준다.
                        hole--;
                    }
                }
            }
        }
        return hole == 0;
        //현재 반복문을 통해 확인했을 때, 열쇠 구멍이 모두 맞아서 남는 구멍이 0이라면 return true
    }

    //90도 회전하는 함수
    private int[][] rotate(int[][] key) {
        int l = key.length;
        int[][] newKey = new int[l][l];

        for (int i = 0; i < l; i++) {
            for (int j = 0; j < l; j++) {
                newKey[j][l - 1 - i] = key[i][j];
            }
        }
        return newKey;
    }

    public static void main(String[] args){
        LockAndKey lk = new LockAndKey();
        int [][] key = new int[][]{{1}};
        int [][] lock = new int[][]{{0}};
        boolean result = lk.solution(key, lock);
        System.out.println(result);
    }
}