문제

고고학자인 “튜브”는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

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

자물쇠와 열쇠 link

  • 제한사항

key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다. lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다. M은 항상 N 이하입니다. key와 lock의 원소는 0 또는 1로 이루어져 있습니다. 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

과정

우선 열쇠 배열을 90도씩 돌리고, 열쇠를 한 칸씩 옮기면서 자물쇠와 일치하는지 확인을 해야겠다는 생각을 했다.

사실 저 생각은 당연한 거고, 그래서 어떤 자료구조를 이용해서 어떻게 구현할 것인지가 문제인데.. 나는 처음에 굳이 2차원 배열을 만들어서 돌려야 하나? 생각해서 열쇠의 돌기 위치와 자물쇠의 홈, 돌기 위치 (i, j)를 각각의 pos_key, pos_lock, pos_not_lock 집합에 저장했다.

그리고 위에 구상한대로 90도씩 열쇠를 돌려가면서 자물쇠 홈에 열쇠의 돌기가 맞는지(pos_lock - key = 공집합), 자물쇠 돌기와 열쇠의 돌기가 겹치지 않는지(pos_not_lock - key = pos_not_lock) 확인했다. 두 가지를 만족하면 true를 반환했다.

주의할 점은 열쇠를 이동하는 범위이다. -len_key + 1 부터 len_lock까지 탐색해야 한다. 처음에 len_key까지 탐색하는 실수를 했다. 주의하자!

테스트 케이스를 확인할 수 없어서 어느 부분이 틀렸는지 모르겠다. 여튼 잘못됨 ㅜㅜ.

def solution(key, lock):
    len_key = len(key)
    len_lock = len(lock)
    pos_key = [] # 열쇠 돌기
    pos_lock = set() # 자물쇠 홈
    pos_not_lock = set() # 자물쇠 돌기

    for i in range(len_key):
        for j in range(len_key):
            if key[i][j] == 1:
                pos_key.append([i, j])

    for i in range(len_lock):
        for j in range(len_lock):
            if lock[i][j] == 0:
                pos_lock.add((i, j))
            else:
                pos_not_lock.add((i, j))

    # 열쇠 90도 회전
    for _ in range(4):
        for i in range(len_key):
            tmp = pos_key[i][0]
            pos_key[i][0] = pos_key[i][1]
            pos_key[i][1] = len_key - tmp - 1
        # 열쇠 한 칸씩 이동하며 맞는지 확인
        for i in range(- len_key + 1, len_lock):
            for j in range(- len_key + 1, len_lock):
                tmp_key = set()
                for x, y in pos_key:
                    tmp_key.add((x+i, y+j))
                # 열쇠 돌기와 자물쇠 홈이 맞고 and 자물쇠 돌기와 겹치는 부분이 없다면 True
                if pos_lock - tmp_key == set() and pos_not_lock - tmp_key == pos_not_lock:
                    return True

    return False

최종 코드

결국 다른 사람의 풀이를 참고해서 자료구조를 2차원 배열로 수정했다. 열쇠와 자물쇠가 맞는지도 집합이 아니라 2차원 배열의 값을 더해서 자물쇠 영역의 값이 전부 1이 되면 True를 반환하도록 해주었다.

아래 참고 사이트에 들어가면 친절하게 그림으로 설명이 되어있다.

from copy import deepcopy

def solution(key, lock):
    len_key = len(key)
    len_lock = len(lock)

    # 열쇠를 90도 돌리는 함수
    def rotate(key):
        ret = [[0] * len_key for _ in range(len_key)]
        for i in range(len_key):
            for j in range(len_key):
                ret[j][len_key - i - 1] = key[i][j]

        return ret

    # 열쇠와 자물쇠가 맞는지 = 자물쇠 배열의 모든 값이 1인지 검사하는 함수
    def check(lock):
        for i in range(len_lock):
            for j in range(len_lock):
                if lock[i][j] != 1:
                    return False
        return True

    # 열쇠와 자물쇠의 배열 값을 더해 자물쇠를 열어보는 함수
    def unlock(x, y, key):
        tmp_lock = deepcopy(lock)
        for i in range(len_key):
            for j in range(len_key):
                if 0 <= i + x < len_lock and 0 <= j + y < len_lock:
                    tmp_lock[i + x][j + y] += key[i][j]

        return check(tmp_lock)

    # 열쇠를 이동하면서 unlock 함수를 호출하는 부분
    for _ in range(4):
        key = rotate(key)
        for i in range(- len_key + 1, len_lock):
            for j in range(- len_key + 1, len_lock):
                if unlock(i, j, key):
                    return True

    return False

참고 사이트