[알고리즘] 자물쇠와 열쇠 (Brute force-LV3)

📘 알고리즘 노트

문제를 풀기위해 구현해야되는 기능 정리

 

필요한 기능

• ✨ 2차원 리스트를 회전하는 기능
• ✨ 자물쇠의 요소가 1로만 채워져 있는지 확인하는 기능
• ✨ 자물쇠 배열확장 후 중앙부분에 기존의 자물쇠 넣기

문제 설명

주어진 조건으로 자물쇠를 풀수 있는지 없는지 확인하는 문제

자물쇠 N X N 그리고열쇠 M X M 는 2차원 행렬

 

조건

열쇠는 회전과 이동이 가능

열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 정답

 

제한사항

• key = (3<=M<=20, M은 자연수)
• lock = (3<=N<=20, N은 자연수)
• M<=N
• key와 lock의 원소는 0 또는 1로 이루어져 있음

2차원 리스트 90도 회전

def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이
    m = len(a[0]) # 열 길이
    result = [[0] * n for _ in range(m)] # 결과 리스트
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = a[i][j]
            # 첫째행 순서대로 -> 마지막 열
            # 둘째행 순서대로 -> 두번째 열
            # 셋째행 순서대로 -> 첫번째 열
            print(j,n-i-1)
    return result
arr = [[1,0,1],
       [0,0,1],
       [1,1,0]]
print(rotate_a_matrix_by_90_degree(arr))

자물쇠의 요소 확인 기능 모두1이면 True 아니면 False

# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
    # 자물쇠 리스트의 크기를 처음에 3배를 해줬으므로
    lock_length = len(new_lock) // 3
    for i in range(lock_length,lock_length*2):
        for j in range(lock_length,lock_length*2):
            if new_lock[i][j] != 1:
                return False
    return True

 

자물쇠 확장 후 중앙에 넣기

n = len(lock) # 기존 자물쇠 행의 길이
new_lock = [[0]*(n*3) for _ in range(n*3)] # 3배로 확장
for i in range(n):
    for j in range(n):
    	new_lock[i+n][j+n] = lock[i][j] # 기존 자물쇠에서 확장한 n만큼으로 할당

전체 코드

# 문제 이해
# 자물쇠를 푸는 방법
# 자물쇠 => NxN, 열쇠 => MxM
# 열쇠는 회전과 이동 가능
# 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 정답

def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이
    m = len(a[0]) # 열 길이
    result = [[0] * n for _ in range(m)] # 결과 리스트
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = a[i][j] # ㅡ |
            print(j,n-i-1)
    return result
arr = [[1,0,1],
       [0,0,1],
       [1,1,0]]
print(rotate_a_matrix_by_90_degree(arr))

# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
    # 자물쇠 리스트의 크기를 처음에 3배를 해줬으므로
    lock_length = len(new_lock) // 3
    for i in range(lock_length,lock_length*2):
        for j in range(lock_length,lock_length*2):
            if new_lock[i][j] != 1:
                return False
    return True

def solution(key,lock):
    n = len(lock)
    m = len(key)
    # 자물쇠의 크기를 기준의 3배로 변환
    new_lock = [[0]*(n*3) for _ in range(n*3)]
    # 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]
            
    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
        for x in range(n * 2):
            for y in range(n * 2):
                # 자물쇠에 열쇠 끼워 넣기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + i] += key[i][j]
                        
                if check(new_lock) == True:
                    return True
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + i] -= key[i][j]
    return False