프로그래머스 - 자물쇠와 열쇠

자물쇠와 열쇠

설명

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

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

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

def rotate(key):
    row = len(key)
    column = len(key[0])
    result = [[0] * row for _ in range(column)]
    for i in range(row) :
        for j in range(column):
            result[j][row-i-1] = key[i][j]
    return result

def check(key, lock, x, y):
    copy = [l[:] for l in lock]
    # 원본건드리면 안됨
    
    for i in range(len(key)):
        for j in range(len(key[0])):
            copy[i+x][j+y] += key[i][j]
            
    for i in range(len(copy)//3, len(copy)*2//3):
        for j in range(len(copy[0])//3, len(copy[0])*2//3):
            if copy[i][j] != 1:
                return False
    return True

def solution(key, lock):
    answer = False
    lockSize = len(lock)
    
    expand = [[0]*(lockSize*3) for _ in range(lockSize*3)]
    for i in range(lockSize):
        for j in range(lockSize):
            expand[i+lockSize][j+lockSize] = lock[i][j]
    # print(expand)
    for _ in range(4):
        key = rotate(key)
        for i in range(lockSize*2):
            for j in range(lockSize*2):
                if check(key, expand, i, j):
                    return True
                # print(expand)

    return answer

• 돌리고 체크하고 밀고 체크하고 반복하면 될듯?
• 사이즈는 20개고 돌리는건 4번이니까 완전탐색 가보자
• 처음에는 키랑 자물쇠랑 크기가 같은 줄 알고 키를 한칸씩 밀고 0으로 채워가며 하려했으나 요번엔 코드 작성하기 전에 문제 제대로 봤다.
• 키가 자물쇠보다 작을 수 있으므로 키를 미는 과정이 조금 길어질 것 같아 다른 방법을 생각했다.
• 미는 과정을 자물쇠를 넓혀서 생각하자.
• 자물쇠를 같은 크기의 공간을 테두리에 패딩한다고 생각하면 key를 모든 칸에 넣어보며 체크 가능하다.
• 방식 자체는 키를 모든 칸에 넣어보고 자물쇠에 해당하는 공간이 전부 1이면 풀리고, 아니라면 키를 돌리고 다시 해보면 된다.
• 이후는 구현만 하면 되는데, 중요한 점 하나는 리스트를 인자로 넘겼을 때 원본을 건드리지 말것.