[Python][파이썬][프로그래머스] 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT)

programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

문제 설명

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

잠겨있는 자물쇠는 격자 한 칸의 크기가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은 돌기 부분을 나타냅니다.

---

입출력 예

keylockresult

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

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

true

입출력 예에 대한 설명

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

---

문제풀이

해당문제는 2차원배열을 활용한 완전탐색 문제이다.

LOCK 배열에 KEY배열을 맞추어가는 문제인데 그림으로 보면 다음과 같다.

왼쪽 위부터 오른쪽 아래까지 하나씩 맞추어보아야 하는 것이다.

이를 위한 방법은 다음과 같다.

1. (Lock)의 크기 + ((key)의 크기 -1) * 2의 백터를 먼저 만들어 준다. (Background)
2. 여기에서 Key를 (0,0)부터해서 <(key)크기+(lock)의크기-1>까지(위의 예에서는 (4,4))까지 돌려준다.
3. 이때 Key와 Lock를 더해주는데 1이면 성립되는것이며, 0이나 2일때는 성립하지 않는다.
4. 성립할때까지 진행하며 end까지도 성립하지 않는다면, Key를 90도 돌려서 다시 시전한다.
5. key가 360도 돌아갈때까지(총4번) 맞는게 있으면 True 출력, 아니면 Faluse출력

1. KEY와 LOCK를 맞추는 부분 구현

- 먼저 Background를 만들고 key와 Lock를 더해주는 부분을 구현하는 부분이다. 해당 함수에서는 Key가 삽입되는 위치(start_i, start_j)를 가지고 오고 끝나는 위치(end)를 가지고 온다.

- 해당 부분에서 Key와 Lock를 더해주는데 1이면 성립되는것이며, 0이나 2일때는 성립하지 않게 하는데, 여기서 중요한 점은 Key를 먼저 Background에 넣은 다음 Lock를 더해주어야 하는 것이다.

- 즉, Key + Lock가 되어야지, Lock + Key가 되면 안된다는 것이다. 이 문제를 풀면서 가장 햇갈렸던 부분인데 왜 그런지 그림으로 살펴보겠다. 아래의 그림은 문제의 예시가 정답이 되는 경우 이다.(key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동한 경우)

Lock를 먼저 넣고 Key를 넣을 때 노란색 음영 표시처럼 0이 표시되어 에러가 난다.

def insert(key, lock, start_i, start_j, end):
    length = (2*len(key))+len(lock)-2 #행렬 백터의 길이
    background = [[0 for i in range(length)] for j in range(length)] #만들어진 행렬백터

    for i in range(len(key)): # Key를 먼저 Background에 넣는다.
        for j in range(len(key)):
            background[start_i+i][start_j+j] = key[i][j]

    for i in range(len(key)-1,end): # 그리고 Lock를 Key가 넣어진 Background에 더해준다.
        for j in range(len(key)-1,end):
            background[i][j] += lock[i-len(key)+1][j-len(key)+1]
            if background[i][j] != 1: #만약 1이 아닌 경우가 있다면 False 리턴
                return False

    return True

2. KEY를 회전시키는 부분 구현

- x위치 값을 y위치 값으로 바꾸고 x위치 값은 최대 위치 값으로 부터 1씩 빼준다.

def rotate(key):
    back_key = [[0]*(len(key)) for i in range(len(key))]
    reverse = len(key)-1
    for i in range(len(key)):
        for j in range(len(key)):
            back_key[j][reverse] = key[i][j]      
        reverse -= 1

    return back_key

3. 최종 코드

- Solution부분에는 Key삽입이 시작되는 위치, Key회전을 적용하는 부분, True를 판별하는 부분이 들어간다.

def rotate(key):
    back_key = [[0]*(len(key)) for i in range(len(key))]
    reverse = len(key)-1
    for i in range(len(key)):
        for j in range(len(key)):
            back_key[j][reverse] = key[i][j]      
        reverse -= 1

    return back_key



def insert(key, lock, start_i, start_j, end):
    length = (2*len(key))+len(lock)-2 #행렬 백터의 길이
    background = [[0 for i in range(length)] for j in range(length)] #만들어진 행렬백터

    for i in range(len(key)): # Key를 먼저 Background에 넣는다.
        for j in range(len(key)):
            background[start_i+i][start_j+j] = key[i][j]

    for i in range(len(key)-1,end): # 그리고 Lock를 Key가 넣어진 Background에 더해준다.
        for j in range(len(key)-1,end):
            background[i][j] += lock[i-len(key)+1][j-len(key)+1]
            if background[i][j] != 1: #만약 1이 아닌 경우가 있다면 False 리턴
                return False

    return True



def solution(key, lock):
    end = len(key) + len(lock) -1
    for k in range(4):
        for i in range(end):
            for j in range(end):
                start_i = i  #Key삽입 시작 위치(y)
                start_j = j  #Key삽입 시작 위치(x)
                if insert(key, lock, start_i, start_j, end) == True:
                    return True
        key = rotate(key) #Key회전 실시


    return False