자물쇠와 열쇠 - '2020 카카오 코딩 테스트'

코딩테스트 연습 - 자물쇠와 열쇠

2차원 배열 key와 2차원 배열 lock가 0과 1로 주어졌을 때, 회전, 상/하/좌/우 이동을 통해서 홈의 맞으면 true, 맞지 않으면 false 를 출력하는 문제 입니다.

 

1. 접근

1. 먼저, 배열의 길이가 최대 20 * 20 이므로, 완전 탐색 이용

2. key 를 이동 시키기 전에 lock의 배열을 3배 키우고, 중앙의 lock의 값을 위치 시킵니다.

3. 3배 키운 lock을 key가 90도 씩 회전 하면서,

4. 한칸씩 이동 하면서 열리지는 확인 합니다.

5. lock + key의 원소의 값이 모두 1인 lock은 열린다고 할수 있습니다.

 

public class Page325_3 {

    // https://programmers.co.kr/learn/courses/30/lessons/60059?language=java
    public static void main(String[] args) {
        int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
        int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
        System.out.print(new Page325_3().solution(key, lock));
    }

    public boolean solution(int[][] key, int[][] lock){
        // 4방향의 회전을 통해서 확인
        for (int rotate = 0; rotate < 4; rotate++) {
            key = rotateMatrixBy90Degree(key);
            if(isOpen(key, lock)) return true;
        }
        return false;
    }

    public boolean isOpen(int[][] key, int[][] lock) {
        int n = lock.length;
        int m = key.length;

        // 자물쇠의 3배 크기의 2차원 배열을 만듬
        int[][] newLock = new int[n * 3][n * 3];

        // 2차원 배열 중앙에 lock 배열을 넣음
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                newLock[i + n][j + n] = lock[i][j];
            }
        }

        // 자물쇠 완전 탐색
        for (int x = 0; x < n * 2; x++) {
            for (int y = 0; y < n * 2; y++) {
                // 자물쇠의 키 삽입
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < m; j++) {
                        newLock[x + i][y + j] += key[i][j];
                    }
                }

                if (check(newLock)) return true;

                // 자물쇠의 키 해제
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < m; j++) {
                        newLock[x + i][y + j] -= key[i][j];
                    }
                }
            }
        }
        return false;
    }

    // 자물쇠의 중간 부분이 모두 1인지 확인
    public boolean check(int[][] newLock){
        int n = newLock.length / 3;
        for (int i = n; i < n * 2; i++) {
            for (int j = n; j < n * 2; j++) {
                if (newLock[i][j] != 1)
                    return false;
            }
        }
        return true;
    }

    // 2차원 리스트 90도 회전하기
    public int[][] rotateMatrixBy90Degree(int[][] a) {
        int n = a.length;
        int m = a[0].length;
        int[][] newArr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                newArr[j][n - 1 - i] = a[i][j];
            }
        }
        return newArr;
    }
}

 

여기서, rotateMatrixBy90Degree() 메서드 구현을 위해서 구글링을 하였습니다. 90도 씩 회전 하기 위해서, newArr[j][n - 1 - i] = a[i][j]; 부분을 외울 필요가 있을거 같습니다. 기존 행렬의 열(j) 부분이 새로운 행렬의 행(j) 으로 변환되고, 새로운 행렬의 열(n - 1 - i) 은 행의 전체 길이값(n) - 1 에서 기존 행렬의 행(i) 를 빼준 값으로 대체 할수 있습니다.