Link: 자물쇠와 열쇠

문제 요약

열쇠를 회전 + 이동 시켜서 자물쇠의 홈을 정확히 맞추고, 돌기 끼리는 겹치지 않아야 한다.
자물쇠의 영역이 모두 1이 되면 열기 성공.

아이디어

1. lockSize(자물쇠 크기)가 3x3 이고, keySize(열쇠 크기)가 3x3일 때, lockSize + keySize * 2 크기의 보드를 만들고 그 중앙에 자물쇠를 복사한다.

2. 열쇠를 90도씩 돌려가며 [0 , 0]부터 순차적으로 끼워보고 자물쇠 영역에 빈 칸이 없는지 계속 확인한다.

주요 코드

1. 보드 생성

        for (i in 0 until lockSize) {
            for (j in 0 until lockSize) {
                board[i + keySize][j + keySize] = lock[i][j]
            }
        }

보드 중앙에 자물쇠 모양 붙여넣기

2. 열쇠 돌리기

    private fun rotate(key: Array<IntArray>): Array<IntArray> {
        val n = key.size
        val rotated = Array(n) { IntArray(n) }
        for (i in 0 until n) {
            for (j in 0 until n) {
                rotated[j][n - i - 1] = key[i][j]
            }
        }

        return rotated
    }

3. 열쇠 덮어쓰기(끼우기)

    private fun applyKey(board: Array<IntArray>, key: Array<IntArray>, x: Int, y: Int) {
        for (i in key.indices) {
            for (j in key.indices) {
                board[x + i][y + j] += key[i][j]
            }
        }
    }

열쇠 값을 보드에 덧셈. 예를 들어 key[i][j] 가 1이면 (i, j) 좌표를 1 증가시킨다.

4. 열쇠 맞춤 확인

    private fun checkUnlocked(board: Array<IntArray>, offset: Int, size: Int): Boolean {
        for (i in 0 until size) {
            for (j in 0 until size) {
                if (board[i + offset][j + offset] != 1) return false
            }
        }
        return true
    }

• offset: 열쇠 크기만큼 늘려놓은 좌측 여백을 맞추기 위함.
• size: 자물쇠 크기

자물쇠 구역이 모두 1이면 자물쇠를 열었다고 판단함.

5. 열쇠 지우기 (원상복구)

    private fun removeKey(board: Array<IntArray>, key: Array<IntArray>, x: Int, y: Int) {
        for (i in key.indices) {
            for (j in key.indices) {
                board[x + i][y + j] -= key[i][j]
            }
        }
    }

자물쇠 구역 중 하나라도 1이 아니라면 열지 못했다고 판단하고, 열쇠를 제거.

6. 반복 루프

        var rotatedKey = key
        repeat(4) {
            rotatedKey = rotate(rotatedKey)

            for (x in 0 until(boardSize - keySize + 1)) {
                for (y in 0 until (boardSize - keySize + 1)) {
                    applyKey(board, rotatedKey, x, y)
                    if (checkUnlocked(board, keySize, lockSize)) return true
                    removeKey(board, rotatedKey, x, y)
                }
            }
        }

열쇠를 회전시켜 보드 위 모든 좌표에 끼워넣기 시도.
자물쇠 영역이 모두 1인지 확인하고, 아니라면 원상태로 복구

요약

1. 보드 초기화 및 중앙에 자물쇠 복사
2. 열쇠를 4회 회전
   1. 회전된 각 열쇠를 보드 위 모든 위치에 이동
   • 덮어쓰기
   • 자물쇠 영역이 모두 1인지 확인
   • 성공 시 true
   • 실패 시 원상복구
3. 4개 열쇠 모두 실패 시 false