자물쇠와 열쇠

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

📖 문제 해결
키를 회전하고 이동하며 넣어보는 모든 경우의 수를 계산하는 완전 탐색 방법을 이용하여 문제를 해결하였습니다. 이 문제에서는 보통의 키와 자물쇠와는 달리 키가 자물쇠 안에 쏙 들어오게 넣지 않아도 됩니다. 즉, 키가 자물쇠 옆으로 삐져나온 형태로 넣어도 됩니다. 따라서 삐져나온 모든 경우의 수를 수월하게 계산하기 위하여 자물쇠의 가로의 길이와 세로의 길이 보다 각각 세 배씩 긴 0으로 된 리스트의 한 가운데에 자물쇠를 넣어 놓은 변형된 형태의 자물쇠 transform_lock 을 문제에서 활용하였습니다. 또한 코드를 간결하게 작성하기 위하여 키를 90도씩 회전하는 rotate_90() 함수와 키와 자물쇠가 딱 맞는지 확인하는test()함수를 따로 작성하여 solution()함수에서 사용할 수 있도록 하였습니다.

# 키를 90도 돌리는 함수
def rotate_90(key) :
    rot_mat = [[0] * len(key) for _ in range(len(key))]
    
    for r in range(len(key)):
        for c in range(len(key)):
            rot_mat[c][len(key)-1-r] = key[r][c]
    
    return rot_mat

# 키와 자물쇠가 딱 맞는 지 확인하는 함수
def test(lock):

    n = len(lock)
    n = n // 3
    
    for r in range(n,n*2):
        for c in range(n,n*2):
        
        	# 모든 값이 1이어야 키와 자물쇠가 딱 맞는 것이므로
            if lock[r][c] != 1 :
                return False
    
    return True

# solution 함수
def solution(key, lock):
    
    n = len(lock)
    m = len(key)
    
	# 자물쇠의 형태를 변형
    transform_lock = [[0]*(n*3) for _ in range(n*3)]

    for i in range(n,n*2):
        for j in range(n,n*2):
            transform_lock[i][j] = lock[i-n][j-n]
    
    # 4가지 회전 방향에 대하여 확인
    for i in range(4):
        key = rotate_90(key)

        for l_row in range(n*2):
            for l_col in range(n*2):
           
				# 자물쇠에 키를 넣어 보기
                for k_row in range(m):
                    for k_col in range(m):
                        transform_lock[l_row+k_row][l_col+k_col] += key[k_row][k_col]
						
                        # 만약 키와 자물쇠가 딱 맞는다면 True 반환
                        if test(transform_lock):
                            return True
				
                # 자물쇠에 넣어 보았던 키를 다시 빼기
                for k_row in range(m):
                    for k_col in range(m):
                        transform_lock[l_row+k_row][l_col+k_col] -= key[k_row][k_col]
      
    # 만약 모든 경우에 대하여 키와 자물쇠가 맞지 않다면 False 반환
    return False