[Programmers] 자물쇠와 열쇠

[문제 설명]

 

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

 

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

 

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

 

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

제한사항

• 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은 돌기 부분을 나타냅니다.

---

입출력 예

key                                lock                                  result

[[0, 0, 0], [1, 0, 0], [0, 1, 1]]

[[1, 1, 1], [1, 1, 0], [1, 0, 1]]

true

입출력 예에 대한 설명

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

 

 

[문제 이해]

 

 

위의 설명에서 나온바와 같이 key 와 lock은 2차원 배열 형태로 주어진다.

 

key 배열을 돌리거나 사방향으로 이동하여 lock부분의 빈 공간을 모두 채울 수 있으면 된다.

 

아래와 같이 2차원 배열을 회전하고 이동시켜서 lock키와 비교시킨다.

 

회전 알고리즘

이동 알고리즘

 

하지만 위와 같이 오른쪽으로 이동한 후 아래쪽으로 이동하여 lock 배열과 맞춰봐야 하지만 아래쪽은 공간이 없으니 별도의 처리가 필요하다.

 

[풀이 과정]

 

우선 기본적으로 key 배열을 돌리기 위한 함수가 필요하다.

    def rotate(key):

        answer = [[0]*n for a in range(n)]

        for i in range(n):
            for j in range(n):
                answer[j][n-i-1] = key[i][j]

        return answer

가로 세로 길이가 n 인 2차원 배열(answer)를 생성한 후

 

key 배열의 x좌표와 y좌표를 answer 배열의 y좌표, n-x-1좌표에 대입하여 반환한다.

 

 

문제는 자물쇠 영역을 벗어난 부분을 무시하여 lock배열과 맞추어 볼 수 있다.

 

그래서 필자는 패딩과 슬라이딩 윈도우 기법을 사용하였다.

 

아이디어는 아래와 같다.

 

3 x 3 -> 7 x 7

우선 3x3 크기의 key 배열을 7x7사이즈로 패딩한다.

# key 값 패딩 탬플릿
arr = [[0]*(2*n+m-2) for _ in range((2*n+m-2))]

# 넘파이 배열로 변환
arr = np.array(arr)

# 중간에 key 삽입
arr[(n-1):-(n-1),(n-1):-(n-1)] = key

 

 

3x3 크기의 2차원 배열을 파싱하고, 해당 배열을 한번씩 돌려보며 lock값과 일치하는 지 비교한다.

한간씩 이돟하며 우하단까지 진행한다.

 

위와같은 작업을 좌상단부터 우하단 까지 한칸씩 이동하며 반복한다.

 

    for i in range(m+n-1):
        for j in range(m+n-1):
            temp = arr[i:i+n,j:j+n].tolist()
            for _ in range(4):
                temp = rotate(temp)

                if temp == lock:
                    return True

 

필자의 경우, 파싱된 key 배열과 lock키를 비교할대 lock 키의 1 값과 0 값을 반전 시켜 key와 lock이 같을 경우(key==lock) True를 반환하도록 설계하였으나,

 

지금 생각해보니 xor 연산을 사용하는 것도 방법이 될 것 같다.

 

    # lock배열 0 1 반전
    for i in range(n):
        for j in range(n):
            if lock[i][j] == 1:
                lock[i][j] = 0
            else:
                lock[i][j] = 1

 

 

[최종 풀이]

import numpy as np

def solution(key, lock):

    def rotate(key):

        answer = [[0]*n for a in range(n)]

        for i in range(n):
            for j in range(n):
                answer[j][n-i-1] = key[i][j]

        return answer

    m = len(key)
    n = len(lock)

    # key 값 패딩 탬플릿
    arr = [[0]*(2*n+m-2) for _ in range((2*n+m-2))]

    # 넘파이 배열로 변환
    arr = np.array(arr)

    # 중간에 key 삽입
    arr[(n-1):-(n-1),(n-1):-(n-1)] = key

    # lock배열 0 1 반전
    for i in range(n):
        for j in range(n):
            if lock[i][j] == 1:
                lock[i][j] = 0
            else:
                lock[i][j] = 1

    for i in range(m+n-1):
        for j in range(m+n-1):
            temp = arr[i:i+n,j:j+n].tolist()
            for _ in range(4):
                temp = rotate(temp)

                if temp == lock:
                    return True
    return False

 

카카오 코딩테스는 문제를 보면 항상 묻는 바는 자명하다.

 

문제가 길고, 구현하기 까다로운 경향이 있지만 방향성이 명쾌하다면 오히려 구현하는데에 주저함이 없다.

 

 

다른 풀이들을 찾아 보았으나 다른분들도 다들 슬라이딩 윈도우 기업을 사용하여 해결하였다.

 

카카오 코딩테스트는 복합한 문자열을 처리하거나, 배열을 다루는 등 구현문제를 위주로 내는 경향이 있다.