자물쇠와 열쇠

문제

2020 KAKAO BLIND RECRUITMENT
https://school.programmers.co.kr/learn/courses/30/lessons/60059

문제 요약

n x n 크기의 자물쇠와 m x m 크기의 열쇠가 주어지는데 key를 회전과 이동을 통해 자물쇠의 빈공간을 채우는 문제,
여기서 영역을 벗어나는 것은 상관 없지만 영역내에서는 정확히 빈칸만 채워져야 자물쇠를 열 수 있다.

ex)

key		lock 	인 상태이면 키를 시계방향으로 한번 돌리고 오른쪽 한칸 아래로 한
0 0 0		1 1 1  	칸 이동하면 자물쇠를 풀 수 있다
1 0 0		1 1 0
0 1 1		1 0 1

시계 방향 회전    오른쪽 한칸    아래로 한칸
key	       key	   key
0 1 0	      0 0 1	   0 0 0
1 0 0	      0 1 0        0 0 1
1 0 0	      0 1 0        0 1 0

풀이과정

위의 과정을 구현하면 되는데

우선 자물쇠가 키보다 크거나 같기 때문에 0으로 초기화된 자물쇠 3배 크기의 배열을 새로 만들어준다.

새 배열의 가운데에 자물쇠의 값을 넣어준뒤

시계방향으로 회전 후 x, y축으로 한칸씩 움직이며 새로운 배열에 key값을 더해준다.

더해준 뒤엔 가운데 자물쇠의 값을 체크하며 1이 아닌값이 있으면 false 없으면 true반환해준다.

false를 받으면 더해줬던 값을 다시 빼준뒤 반복문을 진행한다.

아래의 그림을 보면 더 이해가 편하다.

코드

def check(n, new_lock):  # 가운데에 0인 부분이 있는지 체크
    for i in range(n):
        for j in range(n):
            if new_lock[i + n][j + n] != 1: # 1이 아니면 자물쇠 못품
                return False
    return True

def rotate(m, key):
    new_arr = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            new_arr[i][j] = key[m - j - 1][i]

    return new_arr

def solution(key, lock):
    n = len(lock)
    m = len(key)

    new_lock = [[0] * (n * 3) for _ in range(n * 3)] # 3배크기 배열 생성

    for i in range(n):  # 가운데에 기존 lock 추가
        for j in range(n):
            new_lock[i + n][j + n] = lock[i][j]

    for rot in range(4): # 회전 4번
        key = rotate(m, key)
        for x in range(2 * n):  # x축 이동
            for y in range(2 * n):  # y축 이동
                for i in range(m):  # 자물쇠에 열쇠 넣기
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]

                if check(n, new_lock):
                    return True
                
                for i in range(m):  # 자물쇠에 열쇠 빼기
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    return False