자물쇠와 열쇠 파이썬

def solution(key, lock):
    n,m = len(lock),len(key)
    new_map = [[0]*(2*(m-1)+n) for _ in range(2*(m-1)+n)]
    for i in range(n):
        for j in range(n):
            new_map[m-1+i][m-1+j] = lock[i][j]

    for _ in range(4):
        for i in range(m-1+n):
            for j in range(m-1+n):
                for k in range(m):
                    for l in range(m):
                        new_map[i+k][j+l] += key[k][l]
                flag = True
                for k in range(n):
                    for l in range(n):
                        if new_map[m-1+k][m-1+l] != 1:
                            flag = False
                            break
                if flag:
                    return True
                for k in range(m):
                    for l in range(m):
                        new_map[i+k][j+l] -= key[k][l]
        key = list(zip(*key[::-1]))
    return False

bfs로 푸는건 테스트케이스 7개가 시간초과가 났다..

 

결국 배열의 크기를 확장해서 lock을 배열의 중앙에 두고 key를 옮겨가며 맞춰보는 방법으로 풀었다.