[2020 카카오 블라인드] Q03. 자물쇠와 열쇠 (JAVA)

문제

문제 설명

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 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은 돌기 부분을 나타냅니다.

입출력 예

풀이

조건의 범위가 작아서 완전탐색으로 진행하였다. 다만, lock에 padding을 주어 확장시킨 후 key를 움직이게 하는 방법은 스스로 생각해내지 못했다. 과연 이 상태로 코딩테스트를 보면 한 문제라도 풀 수 있을지 의문이다.. 열공하자...

1. 열쇠로 채워야 할 칸 개수를 targetUnlockCount에 저장한다.
2. lock 배열을 확장하고 중앙에 위치시켜서 paddingLock에 저장한다.
3. key를 4번(0도, 90도, 180도, 270도) 회전시키며 각각의 경우에 자물쇠가 풀리는 지 확인한다.
4. paddingLock의 좌상단부터 우하단까지 key를 이동하며 각각의 경우에 자물쇠가 풀리는 지 확인한다. 모든 잠금이 풀렸고 돌출부가 겹치지 않는 경우가 성공한 경우에 해당한다.

코드

import java.util.Arrays;

class Solution {
    
    private static int targetUnlockCount;
    private static int[][] paddingLock;

    public boolean solution(int[][] key, int[][] lock) {
        getTargetUnlockCount(lock);
        getPaddingLock(key, lock);
        for (int i = 0; i < 4; i++) {
            key = rotateKey(key);
            if (movedKeyFitsLock(key)) return true;
        }
        return false;
    }

    private void getTargetUnlockCount(int[][] lock) {
        for (int[] row : lock)
            for (int cell : row)
                if (cell == 0) targetUnlockCount++;
    }

    private void getPaddingLock(int[][] key, int[][] lock) {
        int newLength = lock.length + 2 * (key.length - 1);
        paddingLock = new int[newLength][newLength];
        for (int[] row : paddingLock) Arrays.fill(row, -1);
        for (int i = 0; i < lock.length; i++)
            for (int j = 0; j < lock.length; j++)
                paddingLock[i + (key.length - 1)][j + (key.length - 1)] = lock[i][j];
    }

    private int[][] rotateKey(int[][] key) {
        int[][] newKey = new int[key.length][key.length];
        for (int i = 0; i < key.length; ++i)
            for (int j = 0; j < key.length; ++j)
                newKey[i][j] = key[key.length - 1 - j][i];
        return newKey;
    }

    private boolean movedKeyFitsLock(int[][] key) {
        for (int i = -20; i <= paddingLock.length; i++)
            for (int j = -20; j <= paddingLock.length; j++)
                if (keyFitsLock(key, i, j)) return true;
        return false;
    }

    private boolean keyFitsLock(int[][] key, int x, int y) {
        int unlockCount = 0;
        for (int i = 0; i < key.length; ++i)
            for (int j = 0; j < key.length; ++j) {
                int newY = y + i;
                int newX = x + j;
                if (isInRange(newY, newX, paddingLock))
                    if (key[i][j] == 1 && paddingLock[newY][newX] == 0) unlockCount++;
                    else if (key[i][j] == 1 && paddingLock[newY][newX] == 1) return false;
            }
        return unlockCount == targetUnlockCount;
    }

    private boolean isInRange(int y, int x, int[][] lock) {
        return y >= 0 && y < lock.length && x >= 0 && x < lock.length;
    }
}

참고

프로그래머스(자물쇠와 열쇠) - Java