[프로그래머스] 자물쇠와 열쇠

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

문제 분석

• 2차원 배열 Key와 Lock이 주어진다
• key는 회전과 이동이 가능하다
• key의 자물쇠 영역을 벗어난 부분은 자물쇠를 여는 데 영향을 주지 않는다
• key가 Lock의 모든 홈을 채워 비어지는 곳이 없으면 자물쇠가 열린다

핵심 아이디어

확장된 Lock 사용

key가 자물쇠의 영역을 벗어나 자유롭게 이동할 수 있도록 Lock의 크기를 증가시킨다

def make_expanded_lock(lock):
    expanded_lock = [[0] * (M * 3) for _ in range(M * 3)]

    for i in range(M):
        for j in range(M):
            expanded_lock[i + M][j + M] = lock[i][j]

    return expanded_lock

본 코드에서는 Lock의 3배에 해당하는 배열을 만든 뒤, 중앙에 Lock의 값을 복사하는 방법을 사용하였다. Key의 크기 < Lock의 크기가 되므로 이제 Key를 자유롭게 이동시키며 비교할 수 있게 되었다

Key 회전

본 코드에서는 Lock과의 비교를 위해 Key가 최대 3번의 회전해야 하므로 함수로 따로 작성한다

def rotate(arr):
    res = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            res[j][N - i - 1] = arr[i][j]
    return res

2차원 배열을 시계 방향으로 90도 회전시키는 코드는 다음과 같다.

자물쇠와 열쇠 비교

1. Lock을 확장시킨 것을 고려하여 비교를 수행할 범위를 설정한다. 본 코드에서는 Lock의 크기를 3배 확장했기 때문에 한 변의 길이는 3M이다. 따라서 M부터 2M까지가 비교할 Lock의 범위가 된다. Key는 Lock을 벗어날 수 있으며, 첫 번째 칸을 기준으로 하기 때문에 Key가 움직일 수 있는 범위는 (M-N+1, 2*M)가 된다
   
2. key의 이동가능 범위에 해당하는 좌표를 함수에 넘겨준 뒤 expanded_lock[i+x_offset][j+y_offset]에 key[i][j]를 더한다.
3. Lock 범위를 검사해 모든 칸의 값이 1이 아니라면 False를 반환하고, 다음 범위를 검사한다.

전체 코드

key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]


def rotate(arr):
    res = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            res[j][N - i - 1] = arr[i][j]
    return res


def make_expanded_lock(lock):
    expanded_lock = [[0] * (M * 3) for _ in range(M * 3)]

    for i in range(M):
        for j in range(M):
            expanded_lock[i + M][j + M] = lock[i][j]

    return expanded_lock


def can_unlock(key, lock, x_offset, y_offset):
    expanded_lock = make_expanded_lock(lock)

    for i in range(N):
        for j in range(N):
            expanded_lock[i + x_offset][j + y_offset] += key[i][j]

    check = True
    for i in range(M):
        for j in range(M):
            if expanded_lock[i + M][j + M] != 1:
                return False

    return True


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

    rotate_90 = rotate(key)
    rotate_180 = rotate(rotate_90)
    rotate_270 = rotate(rotate_180)
    keys = [key, rotate_90, rotate_180, rotate_270]

    check = False
    for key in keys:
        for x_offset in range(M - N + 1, 2 * M):
            for y_offset in range(M - N + 1, 2 * M):
                if (can_unlock(key, lock, x_offset, y_offset)):
                    check = True
                    break

    if check:
        return True
    else:
        return False


print(solution(key, lock))

결과