자물쇠와 열쇠

import copy def solution(key, lock): # 자물쇠의 크기 N, 열쇠의 크기 M # 자물쇠를 양 옆으로 M-1만큼 확장하고, 확장된 칸은 모두 1로 채웁니다. # 이러면 홈 부분의 좌표는 (r + (M-1), c + (M-1))입니다. # 열쇠를 4가지로 회전한 버전을 sliding window 방식으로 # 자물쇠에 대보고, 자물쇠 범위 내에서 XOR한 값들이 모두 1이 아니면 # false를 리턴합니다. N, M = len(lock), len(key) # 우선 홈 부분의 좌표들을 저장해둡니다. rooms = [] for r, row in enumerate(lock): for c, num in enumerate(row): if num == 0: rooms.append( (r + (M-1), c + (M-1)) ) # 자물쇠를 확장합니다. newlock = [ [1] * (2*M - 2 + N) for _ in range(M-1) ] for r, row in enumerate(lock): newlock += [[1] * (M-1) + row + [1] * (M-1)] newlock += [ [1] * (2*M - 2 + N) for _ in range(M-1) ] # 4가지 버전의, 회전한 열쇠들을 마련합니다. # 그대로 turn0 = key # 시계방향 90도 turn90 = copy.deepcopy(key) for r, row in enumerate(key): for c, num in enumerate(row): turn90[c][M-1-r] = num # 180도 turn180 = copy.deepcopy(key) for r, row in enumerate(key): for c, num in enumerate(row): turn180[M-1-r][M-1-c] = num # 반시계방향 90도 turn270 = copy.deepcopy(key) for r, row in enumerate(key): for c, num in enumerate(row): turn270[M-1-c][r] = num # 키들을 대봅니다. keys = [turn0, turn90, turn180, turn270] for k in keys: for r in range(N + M + 1): for c in range(N + M + 1): # 열쇠의 왼쪽 위 부분이 (r, c)입니다. # 즉 열쇠가 커버하는 부분은 (r, c) ~ (r + (M-1), c + (M-1)) # 까지입니다. l = copy.deepcopy(newlock) # 열쇠가 홈을 커버하지 못하면 검사해볼 필요가 없습니다. skip = False for roomr, roomc in rooms: if not (r <= roomr < r+M and c <= roomc < c+M): skip = True break if skip: continue found = True for r1 in range( max(r, M-1), min(M+N-1, r+M) ): for c1 in range( max(c, M-1), min(M+N-1, c+M) ): if k[r1-r][c1-c] ^ l[r1][c1] == 0: found = False break if not found: break if found: return True return False