자물쇠와 열쇠

NXN 크기의 정사각 격자 형태인 자물쇠와 MXM 크기의 정사각 격자 형태인 열쇠가 있다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조이다.

자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만서는 안된다.

자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

0은 홈 부분, 1은 돌기 부분 을 나타낸다.

입력 : 열쇠를 나타내는 2차원 배열 key , 자물쇠를 나타내는 2차원 배열 lock
출력 : 열 수 있으면 true, 열 수 없으면 false

---

자 , 어떻게 할까 생각을 해보자구 ^^

접근

for 90도 회전
	한칸씩 이동
    if 홈이 모두 채워지면
    	 return true
return false

key를 해당 자물쇠의 모든 부분에 가져다 대 보는 식으로 구현을 진행한다. 여기까지 했거든

padding 을 줘서 큰 2차원 배열을 만들어 두고 자물쇠를 가운데에 넣어두고 키를 이리저리 돌려가면서 자물쇠의 모든 부분이 1이 되는 경우 true로 판단한다. !

쉽지 이건 생각은 !

그래서 , 해당 2차원 배열의 크기는 2*(keyLen-1) + lockLen 로 두고 먼저 자물쇠의 값들을 채워준다.

    key_len = len(key)
    lock_len = len(lock)
    board_len = 2 * (key_len - 1) + lock_len
    board = [[0] * board_len for _ in range(board_len)]
    # 새로운 보드를 만드는 코드
    for i in range(key_len - 1, board_len - key_len + 1):
        for j in range(key_len - 1, board_len - key_len + 1):
            board[i][j] = lock[i - key_len + 1][j - key_len + 1]

다음은, 자물쇠를 총 네 번 회전하며 ( 90,180,270,360 ) 회전된 경우에 열쇠를 매칭시키고 열리는가를 확인한다.

def rotate(key, key_len):  # 회전 메소드

    tmp = [[0] * key_len for _ in range(key_len)]
    for i in range(0, key_len):
        for j in range(0, key_len):
            tmp[j][key_len - 1 - i] = key[i][j]
    return tmp

오른쪽으로 90도 회전하는 함수를 생성하여 4번 반복할 예정이다.

다음은 새로 만든 보드판에서 열쇠를 자물쇠에 매칭시키는 함수인 match함수이다.

def match(x, y, board, key, key_len):  # 새로 만든 보드판에 자물쇠와 열쇠를 매치시키는 메소드
    tmp = copy.deepcopy(board)
    for i in range(x, x + key_len):
        for j in range(y, y + key_len):
            tmp[i][j] += key[i - x][j - y]
    return tmp

마지막인 unlock메소드는 match 메소드를 통해 보드판에 열쇠를 적용시킨 후, 자물쇠의 모든 홈(0)부분이 열쇠의 돌기(1)로 알맞게 매칭되었는지를 판별한다.

자물쇠 부분의 모든 1의 개수가 자물쇠 크기의 제곱과 동일하다면 해당 자물쇠와 열쇠가 unlock된 것으로 판단하여 true를 반환하며 그렇지 않다면 false 를 리턴한다.

def unlock(board, board_len, key_len, lock_len):  # 자물쇠와 열쇠가 매칭 된 곳의 unlock 여부 판단
    cnt = 0
    for i in range(key_len - 1, board_len - key_len + 1):
        for j in range(key_len -1, board_len - key_len + 1):
            if board[i][j] == 1:
                cnt += 1

    return True if cnt == (lock_len * lock_len) else False

solution 코드

import copy

def solution(key, lock):
    key_len = len(key)
    lock_len = len(lock)
    board_len = 2 * (key_len - 1) + lock_len
    board = [[0] * board_len for _ in range(board_len)]
    # 새로운 보드를 만드는 코드
    for i in range(key_len - 1, board_len - key_len + 1):
        for j in range(key_len - 1, board_len - key_len + 1):
            board[i][j] = lock[i - key_len + 1][j - key_len + 1]

    # 90도씩 회전하며 검사
    for k in range(4):
        key = rotate(key, key_len)

        for i in range(0, board_len - key_len + 1):
            for j in range(0, board_len - key_len + 1):
                tmp = match(i, j, board, key, key_len)

                if unlock(tmp,board_len,key_len,lock_len):
                    return True

    return False


def rotate(key, key_len):  # 회전 메소드

    tmp = [[0] * key_len for _ in range(key_len)]
    for i in range(0, key_len):
        for j in range(0, key_len):
            tmp[j][key_len - 1 - i] = key[i][j]
    return tmp


def match(x, y, board, key, key_len):  # 새로 만든 보드판에 자물쇠와 열쇠를 매치시키는 메소드
    tmp = copy.deepcopy(board)
    for i in range(x, x + key_len):
        for j in range(y, y + key_len):
            tmp[i][j] += key[i - x][j - y]
    return tmp


def unlock(board, board_len, key_len, lock_len):  # 자물쇠와 열쇠가 매칭 된 곳의 unlock 여부 판단
    cnt = 0
    for i in range(key_len - 1, board_len - key_len + 1):
        for j in range(key_len -1, board_len - key_len + 1):
            if board[i][j] == 1:
                cnt += 1

    return True if cnt == (lock_len * lock_len) else False



if __name__ == '__main__':
    key = [[0,0,0],[1,0,0],[0,1,1]]
    lock = [[1,1,1],[1,1,0],[1,0,1]]
    print(solution(key,lock))

깨달은점
: python 의 list의 깊은 복사와 얕은 복사에서 혼란이 왔음 ㅠ.ㅠ
이거 때메 삽질 1시간 코딩의 늪 ㅠ.ㅠ
진짜 멍텅가리 에흉