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

문제 링크

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

풀이 과정

자물쇠에 열쇠를 가져다 대보는 과정은 아래 사진과 같이 진행할 수 있습니다.

위 과정을 자세히 풀어서 보면, 아래와 같습니다. 위와 같은 보드판이 만들어지면, 가능한 모든 방법으로 자물쇠에 열쇠를 가져다 대볼 수 있습니다.

따라서, 아래와 같이 2 * (keyLen - 1) + lockLen 의 가로 및 세로 크기를 갖는 보드판이 필요합니다.

int[][] board = new int[2 * (keyLen - 1) + lockLen][2 * (keyLen - 1) + lockLen];

for (int i = keyLen - 1; i <= boardLen - keyLen; i++) {
    for (int j = keyLen - 1; j <= boardLen - keyLen; j++) {
        board[i][j] = lock[i - keyLen + 1][j - keyLen + 1];
    }
}

먼저 아래 사진과 같이, 새로 생성된 보드판에 자물쇠를 위치시킵니다.

for (int d = 0; d < 4; d++) {
    key = rotate(key, keyLen);

    for (int i = 0; i <= boardLen - keyLen; i++) {
        for (int j = 0; j <= boardLen - keyLen; j++) {
            int[][] tmp = match(i, j, board, boardLen, key, keyLen);

            if (unlock(tmp, boardLen, keyLen, lockLen)) return true;
        }
    }
}

다음으로, 자물쇠를 총 네 번($90^\circ$→ $180^\circ$ → $270^\circ$ → $360^\circ$) 순서대로 회전( rotate 메소드 )시키며, 각각의 회전된 경우에 대해 열쇠를 매칭( match 메소드 )시키고 열리는가( unlock 메소드 ) 확인해봅니다.

static int[][] rotate(int[][] key, int keyLen) {
    int[][] tmp = new int[keyLen][keyLen];

    for (int i = 0; i < keyLen; i++) {
        for (int j = 0; j < keyLen; j++) {
            tmp[j][keyLen - 1 - i] = key[i][j];
        }
    }

    return tmp;
}

rotate 메소드는 위와 같이 구현됩니다. 새로운 2차원 배열 tmp 의 각 요소에 기존 배열의 요소를 $90^\circ$ 회전시켜 저장합니다.

static int[][] match(int x, int y, int[][] board, int boardLen, int[][] key, int keyLen) {
    int[][] tmp = new int[boardLen][boardLen];

    for (int idx = 0; idx < boardLen; idx++)
        System.arraycopy(board[idx], 0, tmp[idx], 0, board[idx].length);

    for (int i = x; i < x + keyLen; i++) {
        for (int j = y; j < y + keyLen; j++) {
            tmp[i][j] += key[i - x][j - y];
        }
    }

    return tmp;
}

match 메소드는 새로 만든 보드판 상에서, 열쇠를 자물쇠에 매칭시키는 함수입니다. 인자로 받은 (x, y) 좌표에, key 배열의 (0, 0) 좌표의 요소를 시작으로 형태를 유지한 채 매핑시킵니다.

아래 사진은 위의 입력 예시에서, 가능한 모든 (x, y) 좌표 (boardLen - keyLen + 1 ) * (boardLen - keyLen + 1 ) = 7 * 7 = 49 가지의 경우 중, 세 경우를 보여줍니다.

static boolean unlock(int[][] board, int boardLen, int keyLen, int lockLen) {
    int cnt = 0;

    for (int i = keyLen - 1; i <= boardLen - keyLen; i++) {
        for (int j = keyLen - 1; j <= boardLen - keyLen; j++) {
            if (board[i][j] == 1) cnt++;
        }
    }

    return cnt == lockLen * lockLen ? true : false;
}

unlock 메소드는 match 메소드를 통해 보드판에 열쇠를 적용시킨 후, 자물쇠의 모든 홈(0) 부분이 열쇠의 돌기(1)로 알맞게 매칭됐는지를 판별합니다. 이 때 문제의 열쇠의 돌기(1)와 자물쇠의 돌기(1)가 만나면 안된다는 점을 주의해야 합니다. 따라서, 보드판의 모든 요소들이 정확히 1을 만족하는지를 판별해야 합니다. 1의 개수를 모두 세어 그 값이 자물쇠 크기의 제곱과 같다면 true 를 리턴해 자물쇠를 열 수 있다고 판별하고, 아니라면 false 를 리턴해 열 수 없다고 판별해줍니다.

코드

public class Main {
    public static boolean solution(int[][] key, int[][] lock) {
        int keyLen = key.length;
        int lockLen = lock.length;
        int[][] board = new int[2 * (keyLen - 1) + lockLen][2 * (keyLen - 1) + lockLen];
        int boardLen = board.length;

        for (int i = keyLen - 1; i <= boardLen - keyLen; i++) {
            for (int j = keyLen - 1; j <= boardLen - keyLen; j++) {
                board[i][j] = lock[i - keyLen + 1][j - keyLen + 1];
            }
        }

        for (int d = 0; d < 4; d++) {
            key = rotate(key, keyLen);

            for (int i = 0; i <= boardLen - keyLen; i++) {
                for (int j = 0; j <= boardLen - keyLen; j++) {
                    int[][] tmp = match(i, j, board, boardLen, key, keyLen);

                    if (unlock(tmp, boardLen, keyLen, lockLen)) return true;
                }
            }
        }

        return false;
    }

    static int[][] rotate(int[][] key, int keyLen) {
        int[][] tmp = new int[keyLen][keyLen];

        for (int i = 0; i < keyLen; i++) {
            for (int j = 0; j < keyLen; j++) {
                tmp[j][keyLen - 1 - i] = key[i][j];
            }
        }

        return tmp;
    }

    static int[][] match(int x, int y, int[][] board, int boardLen, int[][] key, int keyLen) {
        int[][] tmp = new int[boardLen][boardLen];

        for (int idx = 0; idx < boardLen; idx++)
            System.arraycopy(board[idx], 0, tmp[idx], 0, board[idx].length);

        for (int i = x; i < x + keyLen; i++) {
            for (int j = y; j < y + keyLen; j++) {
                tmp[i][j] += key[i - x][j - y];
            }
        }

        return tmp;
    }

    static boolean unlock(int[][] board, int boardLen, int keyLen, int lockLen) {
        int cnt = 0;

        for (int i = keyLen - 1; i <= boardLen - keyLen; i++) {
            for (int j = keyLen - 1; j <= boardLen - keyLen; j++) {
                if (board[i][j] == 1) cnt++;
            }
        }

        return cnt == lockLen * lockLen ? true : false;
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[][]{{0, 0, 0}, {1, 0, 0}, {0, 1, 1}}, new int[][]{{1, 1, 1}, {1, 1, 0}, {1, 0, 1}}));
    }
}