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

구현문제입니다.

문제를 푸는데 특별한 알고리즘이 필요하지는 않습니다.

 

자물쇠와 열쇠가 주어졌을 때, 열쇠를 이동 및 회전시켜 자물쇠를 열 수 있는가에 대해 묻는 문제입니다.

각각 이차원 배열로 주어집니다.

0과 1로 이뤄져 있는 자물쇠의 2차원 배열의 값을 열쇠로 하여금 전부 1로 바꿔주면 됩니다.

 

문제 조건에 의해, 열쇠는 자물쇠 영역을 벗어날 수 있습니다.

즉, 여기서 알 수 있는 것은 자물쇠 배열을 확장시켜야 한다는 것입니다.

자물쇠 영역을 벗어날 수 있는 키를 맞춰보기 위해서는 확장을 시켜야 합니다.

 

자물쇠와 키를 맞춰본다는 것은 적어도 영역 한 곳은 맞물려 있다는 의미겠죠?

그렇기 때문에 자물쇠와 키의 크기를 각각 n과 m이라고 하면 필요한 영역의 길이는 n+(m-1)*2인 것입니다.

[2를 곱해준 이유는 위, 아래 혹은 좌, 우 각각 (m-1)의 영역 크기가 필요하기 때문입니다.]

자물쇠는 확장된 영역 중앙에 위치하게 하여 중앙을 기준으로 키를 움직이면 됩니다.

처음에 위 그림과 같이 배치를 하여 키를 한 칸씩 움직여 자물쇠의 값이 전부 1인지 확인하면 됩니다.

단, 키를 4방향으로 회전시킨 값을 더해줘야 하기 때문에 같은 위치에서 네 번의 반복문이 필요합니다.

여기서 아래와 같은 공식을 사용하면 실제로 키를 회전시키지 않아도 됩니다.

for (int l = 0; l < len; l++) {
    for (int o = 0; o < len; o++) {
    if (k == 0) {
        // 회전X
        exMap[i + l][j + o] += key[l][o];
    } else if (k == 1) {
        // 1회전
        exMap[i + l][j + o] += key[o][len - l - 1];
    } else if (k == 2) {
        // 2회전
        exMap[i + l][j + o] += key[len - l - 1][len - o - 1];
    } else {
        // 3회전
        exMap[i + l][j + o] += key[len - o - 1][l];
    }
}

exMap은 자물쇠와 키의 길이를 바탕으로 확장시킨 배열입니다.

 

[구현 코드]

class Solution {
    private static int n, m, exLen;
    private static int[][] exMap;

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

        exLen = n + (m - 1) * 2;

        boolean ans = false;
        Loop1:
        for (int i = 0; i < n + (m - 1); i++) {
            for (int j = 0; j < n + (m - 1); j++) {
                // 현재 위치에서 키를 4회전하여 자물쇠와 알맞는지 확인
                for (int k = 0; k < 4; k++) {
                    exMap = new int[exLen][exLen];
                    // 중앙에 자물쇠 셋팅
                    lockSetting(lock);

                    // 자물쇠와 키를 맞춰봄
                    keyIntoLock(key, i, j, k);

                    // 현재 키로 자물쇠를 열 수 있다면(자물쇠의 값이 전부 1이상이라면)
                    if (checkMap()) {
                        ans = true;
                        break Loop1;
                    }
                }
            }
        }
        return ans;
    }

    private static boolean checkMap() {
        for (int l = 0; l < n; l++) {
            for (int o = 0; o < n; o++) {
                // 자물쇠의 빈 부분을 키로 채울 수 있다면
                // 자물쇠 배열의 모든 값은 1임
                // 만약 1보다 크면 키와 자물쇠의 돌기의 접촉이 발생
                if (exMap[l + (m - 1)][o + (m - 1)] != 1) {
                    return false;
                }
            }
        }
        return true;
    }

    private static void keyIntoLock(int[][] key, int i, int j, int k) {
        int len = key.length;

        for (int l = 0; l < len; l++) {
            for (int o = 0; o < len; o++) {
                if (k == 0) {
                    // 회전X
                    exMap[i + l][j + o] += key[l][o];
                } else if (k == 1) {
                    // 1회전
                    exMap[i + l][j + o] += key[o][len - l - 1];
                } else if (k == 2) {
                    // 2회전
                    exMap[i + l][j + o] += key[len - l - 1][len - o - 1];
                } else {
                    // 3회전
                    exMap[i + l][j + o] += key[len - o - 1][l];
                }
            }
        }
    }

    private static void lockSetting(int[][] lock) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                exMap[i + (m - 1)][j + (m - 1)] = lock[i][j];
            }
        }
    }
}