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

이번에 해결해 볼 문제는 프로그래머스에 있는 자물쇠와 열쇠이다.

---

문제 설명

1. 크기 n x n의 자물쇠와 크기 m x m의 열쇠가 있다.(m <= n)
2. 자물쇠와 열쇠 모두 돌기는 1로 돌기가 아닌 홈은 0으로 표현되어 있다.
3. 열쇠를 상하좌우 이동 또는 회전을 통해 자물쇠에 꽂을 수 있다면 True 그렇지 않다면 False를 return 할 수 있다.

문제 예시

• 아래 그림의 경우 열쇠를 90도 회전, 우로 이동, 아래로 이동의 과정을 거쳐 자물쇠에 맞는 열쇠 모양을 얻을 수 있으므로 True를 return 할 수 있다.

문제 해결 아이디어

• 위의 문제를 이해하면 다음을 떠올릴 수 있다.

  • 자물쇠는 가만히 두고 열쇠를 이동시키면서 모양을 맞춰보자.
  • 위의 아이디어를 코드로 구현하기 위해 다음과 같은 트릭을 사용할 수 있다.

  • 크기 n x n의 자물쇠를 크기 3n x 3n의 새로운 자물쇠의 가운데에 두는 것이다.

  • 새로운 자물쇠는 이제 고정 되었으므로 열쇠를 상하좌우로 이동시킬 수 있다.

문제 해결 코드

def rotation(arr, m):
    rotation_arr = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            rotation_arr[j][m-i-1] = arr[i][j]
    return rotation_arr

def check(lock, n):
    for i in range(n, 2*n):
        for j in range(n, 2*n):
            if lock[i][j] != 1:
                return False
    return True

def connect(key, m, lock, row, col, reverse = False):
    if reverse:
        for i in range(m):
            for j in range(m):
                lock[row + i][col + j] -= key[i][j]
        return lock
    else:
        for i in range(m):
            for j in range(m):
                lock[row + i][col + j] += key[i][j]
        return lock

def solution(key, lock):
    n = len(lock)
    m = len(key)
    new_lock = [[0] * (3*n) for _ in range(3*n)]
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]

    for _ in range(4):
        key = rotation(key, m)
        for i in range(2*n):
            for j in range(2*n):
                new_lock = connect(key, m, new_lock, i, j)
                if check(new_lock, n):
                    return True
                new_lock = connect(key, m, new_lock, i, j, True)
    return False

간단한 예시

• 열쇠를 이동시키는 것은 자물쇠를 새롭게 만들면서 해결되었다. 그 다음 회전을 구현하기위해 rotate() 함수를 구현하였고 rotate() 함수를 통해 4가지의 열쇠를 얻을 수 있다.

• 90도 회전된 열쇠가 자물쇠 위를 이동하여 자물쇠에 딱 맞는 경우가 있음을 아래 그림에서 확인할 수 있다.

  • 빨간색 박스 안의 원소가 모두 1이 되는 경우를 check() 함수를 통해 확인할 수 있다.