[python] 프로그래머스_자물쇠와 열쇠 (완전 탐색)

문제

 

풀이

 

열쇠를 적당히 회전/이동시켜서 자물쇠 홈에 딱 맞게 끼워야 한다. 열쇠와 자물쇠 사이즈가 크지 않으므로 완전탐색으로 풀 수 있다. 수월한 풀이를 위해 자물쇠 리스트의 크기를 3배 이상으로 변경(자물쇠를 중간에 두고 나머지는 zero padding)하고 열쇠를 슬라이딩/회전 시키면서 하나씩 확인하면 된다.

 

2차원 리스트를 90도 회전시키는 함수와 자물쇠 리스트의 중간 부분이 모두 1인지 확인하는 함수를 만든다.

메인인 solution 함수에서는 자물쇠의 크기를 3배로 변환하고 새로운 자물쇠 리스트 중간에 기존의 자물쇠를 넣는다. 그리고 4가지 방향과 열쇠가 이동하는 하는 것을 for문을 돈다. 열쇠는 각 위치에서 자물쇠에 넣고 열쇠가 자물쇠에 정확히 들어맞는지 확인하고 다시 자물쇠에서 열쇠를 빼주는 과정을 반복한다. 

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]
    return result

def check(new_lock):
    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)

    new_lock = [[0]*(n*3) for _ in range(n*3)]
    for i in range(n):
        for j in range(n):
            new_lock[n+i][n+j] = lock[i][j]
    #print(new_lock[3][3:6],new_lock[4][3:6],new_lock[5][3:6],sep='\n')
    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+j] += 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+j] -= key[i][j]
    return False

print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],[[1, 1, 1], [1, 1, 0], [1, 0, 1]]))