Programmers#자물쇠와 열쇠

LEVEL :

Level3

문제 요약 :

키를 돌리고 위치를 바꾸어 가며 자물쇠를 여는 문제이다.

해결 방안 :

먼저 문제에 대한 이해는 금방 할 수 있었다.
다만 구현이 문제였다.
크기를 보니 각각 N,M의 크기가 20이 최대여서 브루트포스로 풀 수 있을 거라 생각했지만, 더 효율적인 방법을 찾고자 했다.
그러면서 머리를 굴려 굴려 보아 나온게 key의 모양을 저장해 두어 lock에 배치 할 수 있는 방법이 없을까 생각했다. 결론은 key의 모양을 bfs를 통해서 구하였지만 배치를 함에 있어 브루트포스 방법보다 더 큰 오버헤드가 발생함을 알 수 있었고 반례처리 또한 복잡하다고 느껴져 결국 돌고 돌아 브루트포스 즉 완전탐색 방법을 채택했다.

먼저 키의 회전 각도를 미리 다 구현하여 저장 시켜두고, 키를 모든 위치에서 lock과 대조하기 위해서는 lock의 상하좌우에 key의 길이만큼 빈 공간을 추가해주는 과정이 필요했다.
그렇게 키의 각도와 위치를 바꾸는 과정은 끝났고 비교의 문제였다.
비교는 키와 lock이 겹치는 구간에서 키가 자물쇠의 빈공간을 다 채워 줄 수 있는지 여부에 대해 확인해 주었다.그리고 그 과정에서 두 부분의 돌기 부분이 겹치면 False를 반환해주었다.
최종적인 과정은 아래와 같았다.

Solution

def make_angle_key(key) :
    angles = [key]
    m = len(angles[0])
    for i in range(3):
        last_index = len(angles)-1
        prev = angles[last_index]
        new = [[0]*m for _ in range(m)]
        for i in range(0,m) :
            for j in range(0,m) :
                new[i][j] = prev[m-j-1][i]
        angles.append(new)
    return angles     

def lock_append(lock,n,m) :
    nLen = 2*m+n
    nLock = [[0]*nLen for _ in range(nLen)]
    for i in range(n) :
        for j in range(n) :
            nLock[i+m][j+m] = lock[i][j]
    return nLock

def match(x,y,lock,key,empty_space) :
    m = len(key)
    n = len(lock)
    for i in range(m) :
        for j in range(m) :
            if (m<= x+i < n-m) and (m<= y+j < n-m) :
                if(key[i][j] + lock[x+i][y+j]) != 1 :
                    return False
                else :
                    if key[i][j] == 1 :
                        empty_space -= 1
    return True if empty_space == 0 else False
            
def compare(all_key,lock) :
    n = len(lock)
    m = len(all_key[0])
    sum_lock = 0
    for i in range(n) :
        sum_lock += sum(lock[i])
    empty_space = (n-2*m)*(n-2*m)-sum_lock
    for key in all_key :
        for i in range(0,n-m+1) :
            for j in range(0,n-m+1) :
                isMatch = match(i,j,lock,key,empty_space)
                if isMatch == True :
                    return True
    return False        

def solution(key, lock):
    answer = False
    n = len(lock)
    m = len(key)
    all_key = make_angle_key(key) #Lock을 0,90,180,270 으로 돌림
    lock = lock_append(lock,n,m) #key를 n+2m으로 확장하고 중간에 key를 배치
    answer = compare(all_key,lock)# 모든 방향으로 저장된 lock과 key를 각각 비교한다.
    return answer

출처

프로그래머스 : https://programmers.co.kr/learn/courses/30/lessons/60059