구현 알고리즘 : 자물쇠와 열쇠 - 파이썬 (python)

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

코딩테스트 연습 - 자물쇠와 열쇠

 

- 제한 사항

· key는 M x M (3≤M≤20, M은 자연수) 크기 2차원 배열입니다.

· lock은 N x N (3≤N≤20, N은 자연수) 크기 2차원 배열입니다.

· M은 항상 N 이하입니다.

· key와 lock의 원소는 0 또는 1로 이루어져 있습니다. 이때 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

 

 

* 아이디어 (1)

 

(1) 리스트를 90도 회전시키는 함수 구현

: (x, y)를 90도 회전시키면 (y, len(key_index)-1-x) 값과 같아진다는 규칙을 찾아 함수를 구현함

 

def rotate(key_index):
    rotate_key_index = [[0] * 2 for _ in range(len(key_index))]
    # (x, y) -> (y, x)
    for i in range(len(key_index)):
        for j in range(2):
            rotate_key_index[i][j] = key_index[i][1 - j]

    # (y, x) -> (y, len(key_index)-1-x)
    for i in range(len(key_index)):
        for j in range(2):
            if j == 1:
                rotate_key_index[i][j] = len(key_index) - 1 - rotate_key_index[i][j]
    return rotate_key_index

 

(2) key 리스트와 lock 리스트의 합이 1이 되는지 검사

한 칸씩 이동하며 모든 경우를 체크해야 하는데 두 배열이 모두 3 x 3 이므로 range 오류 발생

해결 방법 → 아이디어 (2) : 자물쇠 리스트의 크기를 3배 이상으로 변경하기

 

 

* 아이디어 (2) : 교재 풀이

 

: 열쇠를 회전하고 이동시켜 자물쇠의 홈에 딱 맞게 끼워 넣는 작업

→ 자물쇠와 열쇠의 크기는 20 x 20 보다 작으므로 완전 탐색을 이용

 

(1) 완전 탐색을 수월하게 하기 위해서 자물쇠 리스트의 크기를 3배 이상으로 변겅

(2) 열쇠 배열을 왼쪽 위부터 시작해서 한 칸씩 이동하는 방식으로 차례대로 자물쇠의 모든 홈을 채울 수 있는지 확인

(3) 자물쇠 리스트에 열쇠 리스트의 값을 더한 뒤에, 더한 결과를 확있했을 때 자물쇠 부분의 모든 값이 정확히 1인지를 확인

→ 1이라면 자물쇠의 홈 부분을 정확히 채운 것

 

 

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)

    # 자물쇠의 크기를 기존의 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+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

 

 

 

https://github.com/501501/codingTest/blob/master/%EA%B5%AC%ED%98%84/A10.py

501501/codingTest