자물쇠와 열쇠 - 2020 카카오 공채 (python)

프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 자물쇠와 열쇠 LV3

https://programmers.co.kr/learn/courses/30/lessons/60059
2차원 배열을 다루는게 익숙해야 풀만할 것 같은 문제.
효율성이 없기 때문에 완전탐색으로 풀면 된다.

👀 깃헙 소스

자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다. 열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

입출력 예

key					lock					result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

솔루션
1) M*2 + N 크기의 보드를 만들고 중앙에 좌물쇠를 배치한다.
2) key를 4번 돌려가며 차례로 이동시킨다
3) 위에서 아래로 열쇠를 이동했을때 중앙의 키가 모두 1이되면 unlock
def rotate90(arr): # 90도 돌리기
def attach(x, y, M, key, board): # 열쇠 넣어보기
def detach(x, y, M, key, board): # 열쇠 빼기
def check(board, M, N): # 모두 1인지 확인

ex) rotate된 열쇠

[(0, 1, 0), (1, 0, 0), (1, 0, 0)]
[(1, 1, 0), (0, 0, 1), (0, 0, 0)]
[(0, 0, 1), (0, 0, 1), (0, 1, 0)]
[(0, 0, 0), (1, 0, 0), (0, 1, 1)]

ex) 중앙에 자물쇠 배치

[[0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 1, 1, 1, 0, 0, 0], 
 [0, 0, 0, 1, 1, 0, 0, 0, 0], 
 [0, 0, 0, 1, 0, 1, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0], 
 [0, 0, 0, 0, 0, 0, 0, 0, 0]]

코드

# 파이썬
def attach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] += key[i][j]

def detach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] -= key[i][j]

def rotate90(arr):
    return list(zip(*arr[::-1]))

def check(board, M, N):
    for i in range(N):
        for j in range(N):
            if board[M+i][M+j] != 1:
                return False;
    return True

def solution(key, lock):
    M, N = len(key), len(lock)

    board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
    # 자물쇠 중앙 배치
    for i in range(N):
        for j in range(N):
            board[M+i][M+j] = lock[i][j]

    rotated_key = key
    # 모든 방향 (4번 루프)
    for _ in range(4):
        rotated_key = rotate90(rotated_key)
        for x in range(1, M+N):
            for y in range(1, M+N):
                # 열쇠 넣어보기
                attach(x, y, M, rotated_key, board)
                # lock 가능 check
                if(check(board, M, N)):
                    return True
                # 열쇠 빼기
                detach(x, y, M, rotated_key, board)
                
    return False