자물쇠와 열쇠

문제링크

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 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

입출력 예에 대한 설명

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

---

문제 풀이

문제를 푸는 발상 자체는 어렵지 않았다.
key와 lock 배열도 최대사이즈가 20이라 소요시간을 크게 고려할 필요도 없었다.

우선 비교하기 전에 key가 lock에 한칸만 겹칠 경우도 고려해서lock에 keySize-1 만큼 0이 담긴 항목을 padding으로 추가해준다

def expendArray(array, keySize, lockSize):
    newArray = array
    for i in range(lockSize):
        newArray[i] = [0 for _ in range(keySize-1)] + newArray[i] + [0 for _ in range(keySize-1)]
    for _ in range(keySize-1):
        newArray.insert(0, [0 for _ in range(lockSize + 2*keySize - 2)])
        newArray.append([0 for _ in range(lockSize + 2*keySize - 2)])
    return newArray

그리고 key를 회전시킬 함수를 구현한다

def rotateArray(array):
    # 90도 회전

    length = len(array)
    newArray = []
    for i in range(length):
        temp = []
        for j in range(length):
            temp.append(array[length - 1 -j][i])
        newArray.append(temp)
    return newArray

그 후 key가 lock과 들어 맞는지를 확인할 함수를 구현한다

def isUnlock(key, expendedMap, keySize, lockSize): # key를 놓을 수 있는 모든 위치를 돌며 체크
    for startX in range(keySize-1 + lockSize):
        for startY in range(keySize-1 + lockSize):
            temp = deepcopy(expendedMap)
            for i in range(keySize):
                for j in range(keySize):
                    temp[startX+i][startY+j] += key[i][j]
            isUnlocked = True
            for i in range(lockSize):
                for j in range(lockSize):
                    if temp[keySize-1 + i][keySize-1 + j] != 1:
                        isUnlocked = False
                        break
                if isUnlocked == False:
                    break
            if isUnlocked == True:
                return True
    return False

그리고 본 함수에서는 key를 90도, 180도, 270도, 360도 회전시킨 함수를
각각 isUnlock함수를 통해 들어맞는 열쇠인지 확인한다.

def solution(key, lock):
    keySize = len(key)
    lockSize = len(lock)
    rotatedKey = key
    expendedMap = expendArray(lock, keySize, lockSize)
    for k in range(4):
        rotatedKey = rotateArray(rotatedKey)
        if isUnlock(rotatedKey, expendedMap, keySize, lockSize):
            return True
    return False

추가적으로 key를 회전시켜주는 rotateArray함수는
zip을 이용하면 좀 더 간단하게 나타낼 수 있었다.

---

최종 완성

from copy import deepcopy

def expendArray(array, keySize, lockSize): # array 가장자리에 각각 keySize만큼 0 추가
    newArray = array
    for i in range(lockSize):
        newArray[i] = [0 for _ in range(keySize-1)] + newArray[i] + [0 for _ in range(keySize-1)]
    for _ in range(keySize-1):
        newArray.insert(0, [0 for _ in range(lockSize + 2*keySize - 2)])
        newArray.append([0 for _ in range(lockSize + 2*keySize - 2)])
    return newArray

def rotateArray(array):
    return list(zip(*array))[::-1]


def isUnlock(key, expendedMap, keySize, lockSize): # key를 놓을 수 있는 모든 위치를 돌며 체크
    for startX in range(keySize-1 + lockSize):
        for startY in range(keySize-1 + lockSize):
            temp = deepcopy(expendedMap)
            for i in range(keySize):
                for j in range(keySize):
                    temp[startX+i][startY+j] += key[i][j]
            isUnlocked = True
            for i in range(lockSize):
                for j in range(lockSize):
                    if temp[keySize-1 + i][keySize-1 + j] != 1:
                        isUnlocked = False
                        break
                if isUnlocked == False:
                    break
            if isUnlocked == True:
                return True
    return False

def solution(key, lock):
    keySize = len(key)
    lockSize = len(lock)
    rotatedKey = key
    expendedMap = expendArray(lock, keySize, lockSize)
    for k in range(4):
        rotatedKey = rotateArray(rotatedKey)
        if isUnlock(rotatedKey, expendedMap, keySize, lockSize):
            return True
    return False

---

다른 풀이 (numpy를 이용)

import numpy as np

def zip_rotate(original):
    rotated = np.array(list(zip(*original[::-1])))
    return rotated

def solution(key, lock):
    key = np.array(key)
    lock = np.array(lock)
    lock_pad = np.pad(lock,((key.shape[0]-1,key.shape[0]-1),(key.shape[0]-1,key.shape[0]-1)),'constant',constant_values=0)
    for k in range(4):
        key = zip_rotate(key)
        for i in range(0,lock.shape[0]+key.shape[0]-1):
            for j in range(0,lock.shape[0]+key.shape[0]-1):
                lock_pad_copy = lock_pad.copy()
                lock_pad_copy[i:(i+key.shape[0]),j:(j+key.shape[0])] = lock_pad[i:(i+key.shape[0]),j:(j+key.shape[0])] + key

                lock_main = lock_pad_copy[(key.shape[0]-1):(lock_pad.shape[0]-key.shape[0]+1),(key.shape[0]-1):(lock_pad.shape[0]-key.shape[0]+1)]
                lock_main = lock_main==1
                if (sum(map(sum,lock_main))==lock.shape[0]**2):
                    return(True)
    return(False)