[문제]
고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 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은 돌기 부분을 나타냅니다.
해결한 방법
// 키를 돌리는 함수 구현, 왼쪽, 중간, 오른쪽 최대 3배의 자물쇠의 크기를 만듬
// 완전 탐색 구현
// 새로운 자물쇠를 만들고
// 새로운 자물쇠 안에서 키를 넣어봄 -> 모두 키인 부분이 1인 경우 참,
// 참일 시 성공을 반환, 실패 시 실패
class Solution {
fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
val m = key.size // 키의 한변
val n = lock.size // 자물쇠의 한변
val newLock = Array(3 * n ){ IntArray(3 * n)} // 뉴 자물쇠
repeat(n){ row ->
repeat(n){ col ->
newLock[n + row][n + col] = lock[row][col] // n 부터 2n 앞까지
}
}
var mKey = key
repeat(4){
if(check(mKey, newLock)){
return true
}
mKey = rotate(mKey)
}
return false
}
fun rotate(key: Array<IntArray>) : Array<IntArray> {
val n = key.size
val rotateArray = Array(n){IntArray(n)}
repeat(n){ row ->
repeat(n){ col ->
rotateArray[col][n - row - 1] = key[row][col]
}
}
return rotateArray
}
// 비교를 해야하는데,
// 새로운 자물쇠 안에서 키를 넣어봄 -> 기존 자물쇠인 부분이 1인 경우 참,
fun check(key: Array<IntArray>, lock: Array<IntArray>) : Boolean{
val n = lock.size
val m = key.size
for(row in 0 until n - m){
for (col in 0 until n - m){ // 시작점 세팅
for(i in key.indices) { // 새로운 자물쇠에 키를 넣음
for (j in key.indices) {
lock[row + i][col + j] += key[i][j]
}
}
if (canOpenDoor(lock)) return true // 키를 확인
for(i in key.indices) { // 지도 원상 복귀
for (j in key.indices) {
lock[row + i][col + j] -= key[i][j]
}
}
}
}
return false
}
// 모든 lock이 1인지 확인하는 함수
fun canOpenDoor(lock: Array<IntArray>) : Boolean{
val n = lock.size
val smallRow = n / 3
for(i in smallRow until smallRow * 2) { // 기존 자물쇠의 요소가 다 1인지 확인
for (j in smallRow until smallRow * 2) {
if(lock[i][j] != 1){
return false
}
}
}
return true
}
}열쇠는 이동과 회전이 가능하다. 이를 통해서 자물쇠의 끝에서 부터 끝까지 회전을 하는 경우까지 모두 탐색을 하여 구해야 한다. 자물쇠의 크기는 열쇠의 크기보다 크거나 같고, 자물쇠의 끝에서 끝까지 비교를 위해서 자물쇠의 크기를 (좌, 우), ㅊ (상, 하)를 고려한 3N * 3N으로 새로운 크기의 자물쇠를 만든다. 새로운 크기의 자물쇠에 키를 차례대로 대입하고, 기존 자물쇠의 영역이 모두 1이면 자물쇠와 키가 일치하는 것으로보고 해결한다.
