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

https://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 함수를 완성해주세요.

 

 

 

---

• 풀이 :

시뮬레이션 문제였습니다.

 

주어진 열쇠와 자물쇠에 대해 열쇠를 4번 회전시켜 현재 열쇠의 모양이 자물쇠의 홈과 일치하는지 확인하는 작업을 실시합니다.

 

구현입니다.

 

1. 열쇠와 자물쇠의 홈이 일치하는지 찾는 check 함수와 열쇠를 회전시키는 rotate 함수로 실행됩니다.

 

2. 열쇠를 회전시키는 rotate 함수는 행렬을 90도만큼 회전시키는 방법을 사용하였습니다. 

 

3. 열쇠와 자물쇠의 홈이 일치하는지 확인하는 함수인 check는 다음과 같이 구현됩니다.

 

- 기존 M*M 의 key 행렬을 상,하,좌,우로 N-1만큼 확장하여 총 (2 * (N - 1) + M) * (2 * (N - 1) + M)의 행렬로 확장합니다.

- 행렬의 가운데 M*M 칸에 key를 덮어씌웁니다.

- 탐색 시작좌표를 (0,0)부터 (N+M-1,N+M-1) 만큼 확장하며 각 시작좌표부터 N*N만큼 lock과 일치하는지 비교합니다.

- 만약 모든 칸이 lock과  일치히지 않는다면(홈이 들어맞는다면) True를 리턴합니다.

 

---

• 소스코드 : 

def rotate(board, key_len): #열쇠 시계방향으로 90도 회전
    tmp = [[0 for _ in range(key_len)] for _ in range(key_len)]
    for i in range(key_len):
        for j in range(key_len):
            tmp[j][key_len - i - 1] = board[i][j]
    return tmp


def check(key, lock, key_len, lock_len):
    arr = [[0 for _ in range(2 * (lock_len - 1) + key_len)] for _ in range(2 * (lock_len - 1) + key_len)]
    
    #열쇠를 자물쇠의 크기만큼 확장
    for i in range(key_len): 
        for j in range(key_len):
            arr[lock_len + i - 1][lock_len + j - 1] = key[i][j]
    
    #확장한 열쇠에서 왼쪽 위의 자표를 (0,0)부터 (key_len + lock_len -1, key_len + lock_len -1)까지 탐색
    for a in range(lock_len + key_len - 1):
        for b in range(lock_len + key_len - 1):
            check = True
            for i in range(lock_len):
                for j in range(lock_len):
                    check = check and (arr[a + i][b + j] != lock[i][j])
            if check: #모든 홈이 일치한다면 참값을 반환
                return True

    return False


def solution(key, lock):
    answer = False
    key_len = len(key) 
    lock_len = len(lock)
    for _ in range(4): # 4번 회전시켜 각 케이스 확인
        answer = check(key, lock, key_len, lock_len) or answer #모든 모양에 대해 열쇠와 자물쇠의 홈이 일치하는지 확인
        key = rotate(key, key_len) # 열쇠 회전
    return answer