[Programmers Java] 자물쇠와 열쇠

[ 동작 순서 ]

1. 맵 확장
   • 배열 생성
   • 자물쇠 위치
2. 열쇠 위치 → 모든 위치 확인
   • 확장맵과 열쇠를 더해줌
   • 자물쇠 범위 확인
     • true → return true
     • false → 열쇠 회전
3. 반복문 종료시 return false → 열쇠와 자물쇠가 맞지 않음

 

맵 확장

- 배열 생성

자물쇠는 N의 크기를 가지고 있다. 열쇠가 배열의 범위를 벗어나 확인이 가능하기 때문에 맵을 N + (M*2) - 2 만큼 확장해 준다.

자물쇠의 크기 + 열쇠 2개 - 겹치는 부분

 

 

- 배열 중심에 자물쇠 위치 시키기

맵의 중심에 자물쇠를 위치시킨다. 확장된 맵에서의 자물쇠의 위치는 열쇠길이-1 부터 시작위치에서 자물쇠의 길이만큼 더해준 값이다.

자물쇠를 확장맵에 위치시키고 나면 다음과 같이 맵이 나타난다.

 

열쇠 위치

2중 반복문을 사용한다. 인덱스의 범위는 (0,0) 부터 자물쇠의 마지막 위치인 (열쇠의 길이+자물쇠의 길이)-1 만큼이다.

 

확장맵 + 열쇠

확장된 맵에 현재 열쇠의 인덱스 (i, j) 부터 열쇠의 크기까지 맵에 더한다

이 결과로 맵에 저장되는 값은 0, 1, 2인데 문제에서 구하고자 하는 값은 1이 된다.

0 : 열쇠와 자물쇠의 홈끼리 만난 경우

1 : 열쇠의 돌기와 자물쇠의 홈이 만난 경우 → 정상

2 : 열쇠의 돌기와 자물쇠의 돌기가 만난 경우

 

자물쇠가 열리는지 확인

전체 맵을 확인 할 필요 없이 자물쇠가 있는 위치만 확인한다. 이 문제의 답은 자물쇠의 홈이 모두 채워지는 경우여야 하기 때문이다.

자물쇠의 범위는 (열쇠의 길이 - 1) ~ (열쇠의 길이 + 자물쇠의 길이 - 1) 이 된다.

해당 범위를 확인하는 check 메서드를 만들어 범위가 전부 1인지 확인한다. check 메서드가 true를 반환한다면 현재 열쇠는 맞는 열쇠가 되기 때문에 true를 return 하고 종료한다. false를 반환한다면 현재 열쇠가 맞지 않기 때문에 방향을 바꿔준다.

방향을 모두 바꿔도 맞지 않는다면 다음 위치로 넘어간다.

 

열쇠 회전

한번에 90도씩 회전시킨다. 90도를 회전시키면 배열의 크기가 3인 인덱스의 매칭은 다음과 같다.

[행][열]

rotate[0][0] = origin[2][0]

rotate[0][1] = origin[1][0]

rotate[0][2] = origin[0][0]

 

rotate[1][0] = origin[2][1]

rotate[1][1] = origin[1][1]

rotate[1][2] = origin[0][1]

 

rotate[2][0] = origin[2][2]

rotate[2][1] = origin[1][2]

rotate[2][2] = origin[0][2]

행과 열을 읽을 때 행을 아래에서부터 위로 읽은 것을 열에 저장한다. 복잡하게 설명하지만 직접 써보면서 풀면 이해가 쉬워진다.

 

전체 코드

public class Solution_자물쇠와열쇠 {

    static int M, N;

    public static boolean solution(int[][] key, int[][] lock) {
        N = lock.length; //자물쇠의 크기
        M = key.length; //열쇠의 크기

        //맵을 자물쇠의 크기에서 열쇠의 크기만큼 확장해줌
        int[][] map = new int[N + (M * 2) - 2][N + (M * 2) - 2];

        //중심에 자물쇠 위치시키기. i/j -> map에 대한 인덱스. k/l -> 자물쇠에 대한 인덱스
        for (int i = M - 1, k = 0; i < M - 1 + N; i++, k++) {
            for (int j = M - 1, l = 0; j < M - 1 + N; j++, l++) {
                map[i][j] = lock[k][l];
            }
        }

        //임시 복사 배열
        int[][] copyMap = new int[map.length][map.length];

        //0,0부터 N-1+M까지 열쇠 두기
        for (int i = 0; i < M + N - 1; i++) {
            for (int j = 0; j < M + N - 1; j++) {
                for (int d = 0; d < 4; d++) {
                    //맵 복사
                    MapCopy(copyMap, map);

                    //열쇠를 복사맵에 더함
                    for (int k = 0; k < M; k++) {
                        for (int l = 0; l < M; l++) {
                            copyMap[i + k][j + l] += key[k][l];
                        }
                    }

                    //자물쇠가 열리는지 확인
                    if (check(copyMap)) { //맞는다면 트루
                        return true;
                    }

                    //방향이 아니라면 돌려줌
                    key = rotate(key);
                }
            }//end j
        }//end i for check all index

        return false;
    }

    private static void MapCopy(int[][] copyMap, int[][] map) {
        //맵 복사함
        for (int k = 0; k < map.length; k++) {
            System.arraycopy(map[k], 0, copyMap[k], 0, map[k].length);
        }
    }

    private static int[][] rotate(int[][] key) {
        int[][] copyKey = new int[M][M];
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                copyKey[i][j] = key[M - 1 - j][i];
            }
        }
        return copyKey;
    }

    private static boolean check(int[][] copyMap) {
        //자물쇠 영역이 전체가 1인지 확인함
        for (int k = M - 1; k < M - 1 + N; k++) {
            for (int l = M - 1; l < M - 1 + N; l++) {
                if (copyMap[k][l] != 1) { //1이 아닌 값이 들어갔다면 돌기끼리 만났거나 홈이 안채워짐
                    return false;
                }
            }
        }
        return true;
    }
}