[알고리즘 문제풀이] 프로그래머스 자물쇠와 열쇠

프로그래머스 위클리 챌린지 3주차 문제를 보고 이건 어떤 걸 이용해서 푸는걸까 궁금했다. 그냥 빡구현 했다가는 너무 비효율적이진 않을까 싶기도 하고 ~ 그래서 오픈채팅방에 해당 문제 관련 키워드나 힌트를 물었더니 빡구현이 맞다고들 하셨다 ! 그리고 관련해서 비슷하지만 조금 더 쉬운 문제로 카카오 기출 문제를 추천해주셨다 ! 그래서 이 문제를 먼저 풀고 위클리 챌린지 3주차 문제를 풀어보려고 한다 !

그래서 오늘 푼 문제는 프로그래머스에서 풀어볼 수 있는 2020 카카오 블라인드 채용 기출 자물쇠와 열쇠 이다.

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한 사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

입출력 예

풀이 방법

이해를 돕기 위해서 위의 예시를 시각적으로 나타낸 그림을 보면 아래와 같다.

큰 틀의 풀이 방법을 살펴보면 아래와 같다.

1. 열쇠는 회전 가능하므로 각 방향 4번에 대해서 아래 과정을 통해 열 수 있는지 탐색해야 한다.
2. 아래의 그림처럼 탐색을 진행할 것이다.
   • 검은색 네모는 lock의 영역이다.
   • 노란색 네모는 key의 영역이다.
   • key가 lock에 들어갈 수 있는 모든 경우의 수를 탐색하기 위해서 왼쪽 위의 노란색 부분부터 오른쪽 아래의 노란색 영역까지 key를 이동시킬 것이다.
   • 위의 과정을 위해서 주황색 영역의 큰 보드를 만들어 사용하였다. 보드는 lock 위치는 lock 원소들 그리고 나머지는 -1로 초기화
3. 위의 설명처럼 key를 이동시키면서 key가 lock에 겹쳐지는 부분은(-1이 아닌 부분) 겹쳐지는 lock 값과 key값을 더한 값을 넣어 주었다.
4. 이제 lock을 쭉 탐색하면서 모든 값이 1이면 잠금이 해제될 수 있는 것이다. ( 0이면 안 채워진 부분 2이면 둘 다 돌기인 부분이니까 ! )

위에 설명한 순서와 비교하면서 코드를 볼 수 있도록 큰 흐름마다 주석을 달아놓았으니 같이 보면 쉽게 이해할 수 있을 것이다 ! 생각보다 빡구현이라 어려운 문제는 아니었다. 이차원 배열을 여러개를 다뤄야 하니까 중첩 for문이 많고 index 관리를 잘 해주기만 한다면 순서대로 차근히 구현만 하면 되는 문제이다 !

코드

import java.util.Arrays;
class Solution {
    public static int[][] rotation(int[][] matrix){
        int size = matrix.length;
        int[][] result = new int[size][size];
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                result[j][size-1-i] = matrix[i][j];
            }
        }
        return result;
    }

    public static boolean isPossible(int[][] key, int[][] lock){
        int m = key.length;
        int n = lock.length;
        int board_size = n + (2*(m-1));
        int[][] board = new int[board_size][board_size];
        int[] arr;

        // key 이동
        int temp;
        boolean index;
        for(int i=0; i<(m-1)+n; i++){
            for(int j=0; j<(m-1)+n; j++){
                index = true;
                // init board
                for(int k=0; k<board_size; k++){
                    arr = new int[board_size];
                    Arrays.fill(arr, -1);
                    board[k] = arr;
                }
                for(int k=0; k<lock.length; k++){
                    for(int l=0; l<lock.length; l++){
                        board[k+m-1][l+m-1] = lock[k][l];
                    }
                }
                // key 이동
                for(int k=0; k<key.length; k++){
                    for(int l=0; l<key.length; l++){
                         // 겹치는 부분 반영
                        if(board[i+k][j+l]!=-1){
                            board[i+k][j+l] += key[k][l];
                        }
                    }
                }
                // lock 검사
                for(int k=0; k<lock.length; k++){
                    for(int l=0; l<lock.length; l++){
                        temp = board[k+m-1][l+m-1];
                        if(temp != 1){
                            index = false;
                            break;
                        }
                    }
                    if(!index) break;
                }
                // 검사 결과 확인
                if(index) return true;
            }
        }
        return false;
    }

    public boolean solution(int[][] key, int[][] lock) {
        for(int i=0; i<4; i++){
            if(i!=0) key = rotation(key);
            if(isPossible(key, lock)) return true;
        }
        return false;
    }
}