[programmers/py] 자물쇠와 열쇠

승민·2024년 4월 29일

programmers

알고리즘

목록 보기

114/171

자물쇠와 열쇠

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

문제 설명

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈(0)과 돌기(1) 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한 사항

key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
M은 항상 N 이하입니다.

풀이

배열의 길이가 크지 않아 완전탐색으로 풀이

간단하게 보면 열쇠를 돌려가면서 lock의 위치와 맞는 모든 경우를 확인하는 문제입니다.

lock을 확장시켜 key가 위치할 수 있는 크기로 만들어줍니다.
key의 값을 확장한 lock의 각 위치에서 더해보며 모든 값이 1이면 True 아니면 False를 반환합니다.

import numpy as np

def rotate(arr): # key 회전
    n = len(arr)
    re = [[0]*n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            re[j][n-1-i] = arr[i][j]
    return re

def check(lock, key, x, y, M, N):
    # lock = 팽창된 자물쇠
    # key = 열쇠
    # x, y = 더할 값, 즉 열쇠의 시작 위치
    # M, N = key, lock(팽창 전) 길이
    ret = True
    
    for i in range(M):
        for j in range(M):
            lock[i+x][j+y] += key[i][j]
            
    for i in range(N):
        if not ret : break
        
        for j in range(N):
            if lock[i+M-1][j+M-1] != 1:
                ret = False
                break
    
    for i in range(M):
        for j in range(M):
            lock[i+x][j+y] -= key[i][j]
    
    return ret
    
def solution(key, lock):
    answer = True
    M = len(key)
    N = len(lock)
    
    # 기존 lock 배열을 확장
    lock = np.pad(lock, ((M-1,M-1), (M-1,M-1)), 'constant', constant_values = 0 )
    
    # 문제는 완전 탐색 
    for i in range(4):
        
        for j in range(M+N-1):
            for k in range(M+N-1):
                if check(lock, key, j, k, M, N):
                    return True
        key = rotate(key)
    
    return False