[프로그래머스] 자물쇠와 열쇠 (Python)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

 

풀이

핵심은 완전 탐색이다. 

자물쇠를 세 배로 키워서 모든 경우의 수로 키를 맞춰본다.

로테이션 코드도 구현이 필요하다. 

 

소스코드

import copy

def lotate(key):
#     000    010     110
#     100 -> 100  -> 001
#     011    100     000
    
#     1행 -> 3열
#     2행 -> 2열
#     3행 -> 1열
    newkey = [[0 for _ in range(len(key))] for _ in range(len(key))]
    for row in range(len(key)):
        for col in range(len(key)):
            newkey[col][len(key)-1-row] = key[row][col]  
    return newkey


def isOpen(key, biglock):
    for i in range(0, len(biglock)-len(biglock)//3):
        for j in range(0, len(biglock)-len(biglock)//3):
            if checkRange(key, biglock, i, j):
                return True
    return False

def checkRange(key, biglock, row, col):
    biglockcopy = copy.deepcopy(biglock)
    for i in range(len(key)):
        for j in range(len(key)):
            biglockcopy[i+row][j+col] += key[i][j]
    
    for i in range(len(biglock)//3, len(biglock)-len(biglock)//3):
        for j in range(len(biglock)//3, len(biglock)-len(biglock)//3):
            if biglockcopy[i][j] != 1:
                return False

    return True
    
def solution(key, lock):
    answer = False
    n = len(lock)
    m = len(key)
    
    req_count = 0    
    biglock = [[0 for _ in range(n*3)] for _ in range(n*3)]
    for i in range(n, n*2):
        for j in range(n, n*2):
            biglock[i][j] = lock[i-n][j-n]
   
    for _ in range(4):
        if i != 0:
            key = lotate(key)  
        if isOpen(key, biglock):
            return True
            
    return answer