자물쇠와 열쇠

programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

import copy

def solution(key, lock):
    M, N, nN = len(key), len(lock), len(lock) + (2 * len(key)) - 2 
    if sum(sum(lock, [])) == N * N: return True # 자물쇠가 열려있음.
    # newLock은 key를 넣는것을 고려하여 lock 주변을 padding한 2차원 배열
    newLock = [[lock[y - M + 1][x - M + 1] if (M - 1) <= y <= (nN - M) and (M - 1) <= x <= (nN - M) else 0 for x in range(nN)] for y in range(nN)]
    
    keys = [key] # key를 회전 시키는것을 고려하여 4 종류로 저장.
    for i in range(3):
        temp = []
        for i in key[:]: 
            temp.append(i[::-1]) # row를 거꾸로 뒤집고 전체의 col과 row를 바꾸면 90도 회전임
        key = [[temp[j][i] for j in range(len(temp))] for i in range(len(temp[0]))]
        keys.append(key)

    opened = [[1 for x in range(N)] for y in range(N)] # lock이 열린 모양
    for y in range(nN - M + 1): # newLock의 범위에서 key를 넣을 수 있는 경우의 범위
        for x in range(nN - M + 1):
            for key in keys: # 한 위치에서 키 4번(회전) 넣어봄
                copy_lock = copy.deepcopy(newLock) # 원본 유지
                for i in range(M): # key를 넣었을 경우 newLock의 값을 알맞게 갱신
                    for j in range(M):
                        copy_lock[y + i][x + j] += key[i][j]

                if [[copy_lock[y][x] for x in range(M - 1, nN - M + 1)] for y in range(M - 1, nN - M + 1)] == opened:
                    return True # 키를 넣었을때 lock 부분이 모두 1이면 lock 해제

    return False # 모든 경우를 탐색해도 자물쇠가 열리지 않았음

→ 구현하는데 범위를 정해야 하는것들이 많아서 헷갈리긴 하지만,

문제 자체의 해결 방법을 찾는것은 어렵지 않았음.

 

copy_lock을 사용할때, newLock이 이중 리스트이고 요소의 추가 삭제가 아닌 요소의 값이 바뀌게 되므로

깊은 복사를 해줘야한다.