문제

풀이

배열 길이가 20 밖에 안 되기 때문에 브루트 포스로도 충분히 풀 수 있다.

열쇠가 자물쇠 영역을 벗어날 수 있으며 회전할 수 있다는 점에 유의하여야 한다.

자물쇠를 좌표축으로 삼고, 열쇠를 회전하고 평행이동하는 모든 경우를 반복하였을 때 자물쇠가 1로만 이루어지는 경우가 하나라도 존재한다면 자물쇠를 열 수 있다. 열쇠와 자물쇠가 겹치는 영역은 두 원소의 합이 1이어야 하고 겹치지 않는 영역은 자물쇠가 1이어야 한다.

코드

def solution(key, lock):
    M = len(key)
    N = len(lock)
    check = True
    for rotate in range(4):
        key = [[key[M - j - 1][i] for j in range(M)] for i in range(M)]
        for y in range(-M + 1, N):
            for x in range(-M + 1, N):
                check = True
                for i in range(N):
                    for j in range(N):
                        if y <= i < y + M and x <= j < x + M:
                            if key[i - y][j - x] + lock[i][j] != 1:
                                check = False
                                break
                        else:
                            if lock[i][j] != 1:
                                check = False
                                break
                    if not check:
                        break
                if check:
                    return True
        
    return False

사족

브루트 포스로 풀 수 있어서 크게 어려운 문제는 아니었는데도 통과할 때까지 한참 걸렸다. 반복문 범위 설정이라든지 두 배열의 인덱스를 통합한다든지 하는 부분에서 사소한 실수가 여럿 있어서 모두 찾아내기까지 실패를 꽤 많이 했다.