[Python] [Programmers] 자물쇠와 열쇠(60059)

💡 문제 해결

1. 충분히 큰 배열을 생성한 후 배열의 가운데에 lock의 값을 저장하는 형식으로 진행
2. key를 회전시키는 함수를 구현 후 4번의 방향으로 돌리는 반복문 실행
3. 회전 시킨 키의 돌기(1) 위치 좌표와 자물쇠의 홈(0) 위치 좌표를 저장
4. 만약 자물쇠에 홈이 존재하지 않는다면 return값을 True로 반환
5. 그렇지 않다면 자물쇠의 홈이 있는 공간마다 열쇠의 돌기부분 중 한 위치를 시작점으로 결합
6. 만약 결합시킨 배열이 적합하다면 True값을 반환
7. 적합하지 않다면 열쇠의 다른 돌기부분을 시작점으로 실행
8. 모든 회전과 모든 돌기부분을 시작점으로 한 결과 적합한 것이 존재하지 않는다면 False반환

📌 자물쇠의 가장 윗 줄 왼쪽 위치의 값을 열쇠의 가장 윗 줄 왼쪽 위치의 값과 합친다 생각하여 시작점을 두었더니
모든 가능성을 고려하지 않는 경우가 생겨 문제점을 찾고, 개선방안을 생각하는데 애먹었던 문제..
📌 정석적인 풀이로는 가상의 len(lock) * 3의 배열을 생성 후 모든 가능성을 판단하는 것이 적합
📌 시작점을 정할 시 pop(0)을 쓰는 방법은 시간을 생각보다 많이 잡아먹을 수 있음

🧾 문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 
그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 
문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 
특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 
열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 
자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 
자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 
열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 
또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 
열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

문제보기

🖨 입출력

📝 풀이

def rotate(key):
    return [list(elem) for elem in zip(*key[::-1])]


def create_key_points(key, M):
    points = []
    for i in range(M):
        for j in range(M):
            if key[i][j] == 1:
                points.append((i, j))
    return points


def create_lock_points(lock, N):
    points = []
    for i in range(N):
        for j in range(N):
            if lock[i][j] == 0:
                points.append((i, j))
    return points


def open_lock(key, lock, N, lock_point, key_points, start):
    arr = [[0] * 61 for _ in range(61)]
    for i in range(N):
        for j in range(N):
            if lock[i][j] == 1:
                arr[i + 20][j + 20] += 1

    arr[20 + lock_point[0]][20 + lock_point[1]] += 1

    for x, y in key_points:
        arr[20 + lock_point[0] + (x - start[0])][20 + lock_point[1] + (y - start[1])] += 1
    
    return arr


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


def solution(key, lock):
    answer = False

    N, M = len(lock), len(key)

    for _ in range(4):
        key = rotate(key)
        key_points, lock_points = create_key_points(key, M), create_lock_points(lock, N)
        if lock_points:
            for lock_point in lock_points:
                for i in range(len(key_points)):
                    start = key_points.pop(0)
                    union = open_lock(key, lock, N, lock_point, key_points, start)
                    if check(union, N):
                        return True
                    key_points.append(start)
        else:
            return True
            
    return answer

• 출처: Programmers
• 링크: https://programmers.co.kr/learn/courses/30/lessons/60059