[프로그래머스] 자물쇠와 열쇠

문제

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

프로그래머스

 

문제 분석

문제를 간단하게 요약하자면 N x N 의 자물쇠 이차원 배열과 M x M 의 열쇠 이차원 배열이 주어진다.

주어진 열쇠를 시계 방향으로 90도씩 회전하고 이동하면서 주어진 자물쇠를 풀 수 있는 지를 물어보는 문제이다. 

열쇠의 돌기 부분이 자물쇠의 홈 부분에 딱 맞아야 자물쇠가 풀린다. (홈과 돌기는 1과 0으로 표기되어 있다.)

 

 

문제의 제한 사항을 확인해보면 N과 M이 3이상 20 이하이고 항상 열쇠 보다 자물쇠의 크기가 크거나 같다.

-> n이 충분히 작으니 완전탐색으로 풀 수 있지 않을까? 

 

문제 풀이

해당 문제는 열쇠를 돌리고 이동하면서 가능한 모든 가능성을 체크해 보는 방법 밖에 없다고 생각했다.

위의 그림처럼 키를 회전시켜 가면서 자물쇠와 맞는 지 체크해보고 맞지 않으면 한 칸 이동해서 또 회전시켜가면서 맞는지 확인해 본다

이런 과정을 반복한다면 해당 문제를 풀 수 있을 것이다.

 

해당 문제를 풀기 위해서 아래와 같은 작업들이 필요할 것이다.

• 열쇠를 어떻게 이동 시킬까? 
• 열쇠를 어떻게 회전 시킬까?
• 자물쇠가 풀린다는 것은 어떻게 알 수 있을까?

 

열쇠를 어떻게 이동시킬까?

나에게는 이 부분이 제일 골치 아팠다..

이중 배열 안에서 하나의 원소를 완전탐색하는 건 많이 해봤는데 이중 배열 안에서 이중 배열을 완전탐색 하려고 하니

어떻게 구현해야 할지 감이 안 왔다.

 

다른 자료들을 참고해 가면서 깨닫게 된 것은 기준을 하나 잡는 것이다.

열쇠 이중 배열의 첫 번째 원소를 기준으로 삼고, 이 기준을 옮기는 것이다.

 

기준의 위치를 알고 열쇠의 길이를 안다면 우린 열쇠의 다른 원소들의 위치도 알 수 있는 것이다.

잘 이해가 되지 않는다면 이따 코드를 통해 다시 이해해 보자 

 

열쇠를 어떻게 회전시킬까?

그냥 이해하려고 한다면 어떻게 해야 할지 감이 오지 않는다.

위처럼 그림을 그려보면 어떻게 키를 회전시킬 수 있을지 알 수 있다.

 

회전시켜보면 다음과 같이 4가지의 경우가 나온다. 

1. 기본 
2. 기본에서 행과 열이 바뀌었다. 근데 바뀐 열이 끝에서부터 시작된다.
3. 기본에서 행과 열은 유지하지만, 행이 끝에서 부터 시작한다.
4. 기본에서 행과 열이 바뀌었고 행이 끝에서 부터 시작한다.

자물쇠가 풀린다는 것을 어떻게 알 수 있을까?

탐색할 때마다 자물쇠와 열쇠의 겹치는 부분을 더해준다. 만약 자물쇠의 모든 원소가 1이라면 자물쇠가 풀릴 것이다.

 

우린 자물쇠의 크기를 확장해 줄 것이다.

확장된 자물쇠의 길이 = 열쇠 길이 * 2 + 자물쇠 길이 - 2

1. 탐색할 때 마다 확장된 자물쇠를 만들어 주고 확장된 자물쇠의 가운데에 기존 자물쇠 내용을 복사한다.
2. 그리고 열쇠의 내용도 확장된 자물쇠에 더한다.
3. 기존 자물쇠 부분만 내용을 확인하면서 모든 원소가 1인지 체크한다.

코드

public class LockAndKey {
    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.println(solution(key, lock));
    }
    public static boolean solution(int[][] key, int[][] lock) {
        
        // 자물쇠의 기준
        // 확장된 자물쇠에서 기존의 자물쇠 위치를 찾기 위해 필요
        int offset = key.length - 1;

        for (int r = 0; r < key.length + lock.length - 1; r++) {
            for (int c = 0; c < key.length + lock.length - 1; c++) {
                // 이 반복문을 통해 열쇠의 기준을 이동 시킨다.
                
                for (int rotate = 0; rotate < 4; rotate++) {
                    // 4번 회전시키기 위한 반복문
                    
                    // 확장된 자물쇠를 만든다.
                    int newLockSize = key.length * 2 + lock.length - 2;
                    int[][] newLock = new int[newLockSize][newLockSize];
                    for (int i = 0; i < lock.length; i++) {
                        for (int j = 0; j < lock.length; j++) {
                            newLock[i + offset][j + offset] = lock[i][j];
                        }
                    }

                    // newLock 에 해당 key 를 더한다.
                    match(newLock, key, r, c, rotate);
                    
                    // 해당 키가 자물쇠를 열 수 있는지 확인한다.
                    if(check(newLock, offset, lock.length)){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public static void match(int[][] newLock, int[][] key, int row, int col, int rotate) {
        int keyLen = key.length;
        for (int i = 0; i < keyLen; i++) {
            for (int j = 0; j < keyLen; j++) {
                switch (rotate){
                    case 0:
                        newLock[i + row][j + col] += key[i][j];
                        break;
                    case 1:
                        newLock[i + row][j + col] += key[j][keyLen-1 - i];
                        break;
                    case 2:
                        newLock[i + row][j + col] += key[keyLen-1 - i][keyLen-1 - j];
                        break;
                    case 3:
                        newLock[i + row][j + col] += key[keyLen-1 - j][i];
                        break;
                }
            }
        }
    }

    public static boolean check(int[][] newLock, int offset, int lockLength) {
        for (int i = 0; i < lockLength; i++) {
            for (int j = 0; j < lockLength; j++) {
                if (newLock[i + offset][j + offset] != 1) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

배운 점

이중 배열 안에서 이중 배열을 어떻게 옮겨가면서 비교를 해야 할지 감이 잡히지 않았는데

이번 문제를 통해서 내가 이해할 수 있는 방식으로 정리할 수 있었다.

 

이중 배열의 기준을 옮긴다고 생각하면 된다.

기준의 위치에서 해당 배열의 길이를 알고 있다면 다른 원소들의 위치도 찾을 수 있다.

 

참고 자료

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