자물쇠와 열쇠

• M과 N이 작기 때문에, 그냥 열쇠를 한칸씩 움직여 대어보면서 자물쇠가 열리는지 확인해 보면 된다.
• 자물쇠가 열리는지를 확인하는 것은 모든 자물쇠 칸이 다 맞물렸는지 체크해보면 된다. 시간복잡도는 O(n^2).
• 열쇠를 움직이는 것은, 열쇠의 각 칸들이 자물쇠의 몇번 칸에 대응되는지를 다 계산해주면 된다. 시간복잡도는 O(m^2).
• 열쇠는 왼쪽 윗부분을 자물쇠 기준 (-m,-m)부터 (n,n)까지 움직여보면 되고 4번 회전을 시켜볼수 있으니까 4*(m+n)^2 번 이동및 회전시키면 된다.
• 총 시간복잡도는 O((m+n)^2 * (m^2 + n^2)) = O(n^4)
• 모든 칸에 대해서 비교하는 대신, 열쇠의 돌기에 해당되는 칸들만 모아서 이동/회전 시키고, 자물쇠의 홈들에 해당되는 칸들과 비교하는 방법도 있다. 자물쇠가 열리는지 확인하는 것이 O(m^2)에 가능해져서 총 시간복잡도가 O(n^2*m^2)이 되지만 이것은 사실 별 차이 없고.. 그냥 코딩이 조금 더 깔끔해서 이쪽으로 구현했다.

"""Solution code for "Programmers 60059. 자물쇠와 열쇠".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/60059
- Solution link: http://www.teferi.net/ps/problems/programmers/60059
"""


def solution(key, lock):
    key_size, lock_size = len(key), len(lock)

    key_pos = set()
    for r, key_row in enumerate(key):
        key_pos.update((r, c) for c, val in enumerate(key_row) if val == 1)
    lock_pos = set()
    for r, lock_row in enumerate(lock):
        lock_pos.update((r, c) for c, val in enumerate(lock_row) if val == 0)

    for _ in range(4):
        key_pos = {(c, key_size - r) for r, c in key_pos}
        for dr in range(-key_size, lock_size):
            for dc in range(-key_size, lock_size):
                moved = {(r + dr, c + dc)
                         for r, c in key_pos
                         if 0 <= r + dr < lock_size and 0 <= c + dc < lock_size}
                if moved == lock_pos:
                    return True
    return False