[프로그래머스] 구현 - 자물쇠와 열쇠

문제 요약  자물쇠와 열쇠

• 특이한 형태의 자물쇠와 열쇠가 있다.

• 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1 인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있다.

• 자물쇠에는 홈이 파져있고 열쇠 또한 홈과 돌기 부분이 있다. 열쇠는 회전과 이동이 가능하며, 열쇠 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열린다.

• 자물쇠 영역을 벗어난 부분에 있는 열쇠와 홈의 돌기는 자물쇠를 여는데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기부분과 자물쇠의 홈 부분이 정확히 일치해야하며

 

• 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안 된다. 자물쇠 모든 홈을 채워 비워있는 곳이 없어야 한다.

아이디어  

회전 행렬 에대한 개념이 필요하다.

2D 리스트의 index 에 대한 이해가 필요하다. (어떤 기능이 가능하고 불가능한지 numpy와 혼동하기 쉽다.)

 

Lock 에 Key 를 각각 껴보기 위해서는 Key 의 블록들이 이동해야한다. 하지만 각 원소를 이동시키는 것은 구현이 어렵다. 간단하게 Lock의 크기를 키워서 key 를 커진 Lock을 순회하며 껴보면 된다. 

 

※ 주의 사항: 더 큰 list 에 작은 list 의 값들을 복사하기 위해서는 전체 원소를 돌며 복사해야 한다. 한번에 복사하는 방법은 list에 없다. 

 

import copy

def check(tmp_ex_lock, N, M):
    for i in range(N):
        for j in range(N):
            if tmp_ex_lock[N+i][N+j] != 1:
                return False
    return True
        

def solution(key, lock):
    answer = False
    
    M = len(key)    
    N = len(lock)
    ex_lock = [[0]*(3*N) for i in range(3*N)]
    
    for i in range(N):
        for j in range(N):
            ex_lock[N+i][N+j] = lock[i][j]
            
    for k in range(4):
        key = list(zip(*key[::-1]))    
        for i in range(2*N):
            for j in range(2*N):  
                tmp_ex_lock = copy.deepcopy(ex_lock)
                for r in range(M):
                    for c in range(M):
                        tmp_ex_lock[i+r][j+c] += key[r][c]
                if check(tmp_ex_lock, N, M):
                    answer = True
                    return answer
    return answer