[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 자물쇠와 열쇠 - 자바(JAVA)

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

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

 

문제 해석

자물쇠는 N*N 크기의 정사각 격자의 형태입니다.

열쇠는 M*M 크기인 정사각 격자의 형태입니다.

 

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다.

열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리는 구조입니다.

 

열쇠의 돌기와 자물쇠의 돌기가 만나면 안 된다.

모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있다.

 

열쇠로 자물쇠를 열 수 있다면 true 없다면 false 반환

 

0은 홈 부분 1은 돌기 부분

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

Key를 90도 회전하게 되면 다음과 같이 구성됩니다.

동그라미는 홈 네모는 돌기

이 그림을 오른쪽으로 한 칸 이동시키고 아래로 한 칸 이동시키면 다음과 같이 구성되며 홈 부분을 정확히 모두 채울 수 있습니다.

 

문제 풀이 전 설계

N의 크기가 크지 않기 때문에 완전 탐색이 가장 먼저 떠오릅니다.

 

이동할 수 있는 방법은 총 6가지입니다.

1. 시계방향 회전

2. 반시계 방향 회전

3~6. 상하좌우 이동

 

처음에는 key의 돌기 부분이 홈보다 작아지게 되면 return 하는 백 트레킹을 생각하였습니다.

하지만 그러면 계속 한쪽 방향으로 회전하거나 상하 또는 좌우 이동을 무한 번으로 수행할 수 있다고 판단했습니다.

즉, false를 판단하기 어려워 보임

 

그래서 방문 체크를 해줘야 할 것 같은데 아이디어가 잘 떠오르지 않습니다.

 

풀이

 

https://www.youtube.com/watch?v=I1App3qLi6o

위의 아이디어를 떠올리는 게 핵심 같습니다.

Lock을 확장시키고 Key를 하나씩 대조해보는 작업을 수행합니다.

 

1. 큰 영역의 2차원 배열을 잡는다.

2. 자물쇠를 영역의 중앙에 복사합니다.

3. 색칠한 부분은 1, 아닌 부분은 0이 들어갑니다.

4. 키를 대입하면서 검사합니다. 만약 값이 2가 되면 돌기가 겹쳤다고 판단합니다.

5. 자물쇠 영역이 모두 1인지 검사합니다.

 

코드

class Solution {
    
    void match(int[][] arr, int[][] key, int rot, int y, int x){
        int n = key.length;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(rot== 0){
                    arr[y+i][x+j] += key[i][j];
                } else if(rot ==1){
                    arr[y+i][x+j] += key[j][n - 1 - i];
                } else if(rot ==2){
                    arr[y+i][x+j] += key[n - 1 - i][n - 1 - j];
                } else{
                    arr[y+i][x+j] += key[n - 1 - j][i];
                }
            }
        }
    }
    
    boolean check(int arr[][], int offset, int n){
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(arr[offset + i][offset + j] != 1){
                    return false;
                }                                
            }
        }
        return true;        
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        
        int offset = key.length - 1;
        
        for(int y= 0; y< offset + lock.length ; y++){
            for(int x=0; x< offset + lock.length ; x++){
                for(int rot = 0; rot < 4; rot ++){
                    int[][] arr = new int[58][58];
                    for(int i=0; i< lock.length; i++){
                        for(int j=0; j<lock.length; j++){
                            arr[offset + i][offset + j] = lock[i][j];
                        }
                    }
                    
                    match(arr, key, rot, y, x);
                    if(check(arr, offset, lock.length)){
                        return true;
                    }
                    
                }
            }
        }
        
        
        return false;
    }
}

 

 

 

출처

https://www.youtube.com/watch?v=I1App3qLi6o