My Solution

문제에서 주어진 N과 M의 범위가 3~20사이로 크지 않기 때문에 모든 경우의 수에 대입해보는 완전탐색으로 접근하였다.
문제에서 설명한 대로 rotate함수를 통해 열쇠를 시계방향으로 90도씩 회전하면서 오른쪽과 아래쪽으로 한칸씩 열쇠를 움직이면서 자물쇠에 직접 대입했다. 이때, 열쇠와 자물쇠의 크기를 맞추기 위해 newKey라는 함수를 통해 자물쇠의 칸에 들어갈 열쇠를 새로 만들었다. newKey에는 offset을 인자로 주어 자물쇠와 열쇠가 겹치는 부분을 새로운 열쇠에 반영하도록 하였다.
또한, validation함수에서는 열쇠가 자물쇠와 맞는지 검증하는 작업을 수행하는데, 위의 newKey를 통해 열쇠와 자물쇠의 크기를 맞추어두었기 때문에 단순히 2차원 리스트를 돌면서 자물쇠와 열쇠의 각 칸의 합이 1이 아니라면 False를 반환하도록 하였다.

def solution(key, lock):
    m, n = len(key[0]), len(lock[0])

    for direction in range(4):
        key = rotate(key)
        for i in range(n+m-1):
            for j in range(n+m-1):
                k = newKey(n, key, (i,j))
                if validation(k, lock) == True:
                    return True
    return False

# 열쇠를 시계방항으로 90도 회전
def rotate(key):
    n = len(key)
    result = [[0]* n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            result[j][n-(i+1)] = key[i][j]
    return result

# 자물쇠의 크기에 맞는 열쇠를 생성
def newKey(lockSize, key, offset):
    result = [[0]*lockSize for _ in range(lockSize)]
    x,y = offset
    n = len(key)
    for i in range(n):
        if x - i >= 0 and x - i < lockSize:
            for j in range(n):
                if y - j >= 0 and y - j < lockSize:
                    result[x-i][y-j] = key[n-(i+1)][n-(j+1)]
    return result

# 열쇠가 자물쇠에 맞는지 검사
def validation(key, lock):
    for i in range(len(lock)):
        for j in range(len(lock)):
            if key[i][j] + lock[i][j] != 1:
                return False
    return True

# 디버깅용 열쇠 출력 함수
# def printKey(key):
#     for i in range(len(key)):
#         for j in range(len(key)):
#             print(key[i][j], end=" ")
#         print("")
#     print("")

행렬 회전 함수

n * m 크기의 행렬을 시계방향으로 90도 회전하는 함수이다. 나중에 다른 문제에서 사용할 수 있을 것 같아 정리해두었다.

def rotate(a):
	n = len(a)
    m = len(a[0])
    result = [[0]* n for _ in range(m)]
    
  	for i in range(n):
    	for j in range(m):
      		result[j][n-i-1] = a[i][j]
  	return result

• 2020 KAKAO BLIND RECRUITMENT 자물쇠와 열쇠