문제
문제 설명
고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 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은 돌기 부분을 나타냅니다.
입출력 예
| key | lock | result |
|---|---|---|
| [[0, 0, 0], [1, 0, 0], [0, 1, 1]] | [[1, 1, 1], [1, 1, 0], [1, 0, 1]] | true |
풀이
조건의 범위가 작아서 완전탐색으로 진행하였다. 다만, lock에 padding을 주어 확장시킨 후 key를 움직이게 하는 방법은 스스로 생각해내지 못했다. 과연 이 상태로 코딩테스트를 보면 한 문제라도 풀 수 있을지 의문이다.. 열공하자...
- 열쇠로 채워야 할 칸 개수를
targetUnlockCount에 저장한다. lock배열을 확장하고 중앙에 위치시켜서paddingLock에 저장한다.key를 4번(0도, 90도, 180도, 270도) 회전시키며 각각의 경우에 자물쇠가 풀리는 지 확인한다.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;
}
}