[PRO] 자물쇠와 열쇠

문제에서 N과 M의 최대값이 20인걸 통해 시간복잡도가 매우 높은 방법으로 접근해도 되겠다고 생각했다. 4중 for문이 들어가는데 백준의 체스판 다시 칠하기와 유사하다고 생각했다.

회전하는 방법은 예시를 적어놓고 귀납적으로 추리했다.

def right_rotation(two_dim_list, M): # 2차원 리스트 오른쪽으로 한번 회전한 결과 반환
    new_two_dim_list = [[0]*M for _ in range(M)]
    for i in range(M):
        for j in range(M):
            if two_dim_list[i][j]:
                new_two_dim_list[j][M-i-1]=1
    return new_two_dim_list

def check_all_fill(copied_extended_lock,N): # 자물쇠를 열었는지 체크
    for i in range(N):
        for j in range(N):
            if copied_extended_lock[i+N][j+N] != 1: # 겹치면 2
                return False
    return True

def solution(key, lock):
    M, N = len(key), len(lock)
    extended_lock = [[0]*(N*3) for _ in range(N*3)]
    
    for i in range(N):
        for j in range(N):
            if lock[i][j]:
                extended_lock[i+N][j+N] = 1
    
    # keys:가능한 모든 방향
    keys = [key]
    for _ in range(3):
        key = right_rotation(key, M)
        keys.append(key)
    
    for key in keys:
        for dx in range(3*N-M+1):
            for dy in range(3*N-M+1):
                copied_extended_lock = [row[:] for row in extended_lock]
                for i in range(M):
                    for j in range(M):
                        if key[i][j]==1:
                            copied_extended_lock[i+dx][j+dy] += 1
                
                if check_all_fill(copied_extended_lock, N):
                    return True
    return False

• 넉넉하게 3*N으로 했는데 N+M+M-2만큼만 해도 된다. key와 lock 한칸이 겨우 겹치는 부분까지만 두면 된다.
• 회전하는 방법 생각할때 읽는 방향을 생각하면 더 편하게 접근 가능할 것 같다.