[프로그래머스 - lv3] 자물쇠와 열쇠 - python

문제링크 : 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 함수를 완성해주세요.

제한사항

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

 

문제접근

1. key 배열을 lock에 대입하여 찾을 때, 배열 범위를 벗어나지 않도록 lock배열에 적당한 padding을 줍니다.

2. lock 배열을 전체 순회하며 각각의 인덱스위치에서 key 배열을 이용해 자물쇠를 열 수 있는지 확인합니다.

3. 열 수 있다면 true를 반환하고 열 수 없다면 배열을 시계방향으로 90도 회전시킵니다.

4. 2번으로 돌아가 다시 확인합니다.

5. 회전을 모두 마쳤다면 False를 반환합니다.

 

주의 할 점

문제를 잘 읽어보면 열쇠의 돌기와 자물쇠의 돌기가 만나면 안된다는 조건이 있습니다.

즉, key[row][col] 이 1일때 lock[row][col]도 1이면 안된다는 얘기입니다.

이 부분만 예외처리를 해 주면 어렵지 않게 풀 수 있습니다.

 

 

소스코드

"""
    시뮬레이션 문제로 생각하고, 문제 조건 그대로 구현해서 풀었습니다.
    lock 배열에 key의 크기만큼 -1로 패딩을 주어 키의 위치를 옮겼을때 인덱스를 벗어나지 않도록 했습니다.
    예) key의 크기가 2x2 이고 lock의 크기가 3x3인
        [1,0,1]
        [0,1,0]
        [1,1,1]
        배열이라면 상하좌우 key의 길이 - 1 만큼의 padding을 주어
       [-1,-1,-1,-1,-1]
       [-1, 1, 0, 1,-1]
       [-1, 0, 1, 0,-1]
       [-1, 1, 1, 1,-1]
       [-1,-1,-1,-1,-1]
       형태의 5X5 lock 배열을 만듭니다.
    key배열을 시계방향으로 회전시키고 새로 만든 배열을 순회하며 자물쇠를 열 수 있는지 확인합니다.
    0도 90도 180도 270도로 key배열을 회전시켜도 자물쇠를 열 수 없으면 False를 반환합니다.
"""
 
 
def set_padding(key, lock):
    """ 입력 lock 배열에 패딩을 주는 함수. """
    lockLength = len(lock)
    keyLength = len(key) - 1
    paddingLength = lockLength + (keyLength * 2)
 
    arr = [[-1] * paddingLength for _ in range(paddingLength)]
 
    for i in range(keyLength, paddingLength - keyLength):
        for j in range(keyLength, paddingLength - keyLength):
            arr[i][j] = lock[i-keyLength][j-keyLength]
 
    return arr
 
 
def rotate_key(key):
    """ 키를 회전시키는 함수. 시계방향으로 90도 회전시킨다. """
    n = len(key)
 
    newKey = [[0] * n for _ in range(n)]
 
    for row in range(n):
        for col in range(n):
            newKey[col][n-1-row] = key[row][col]
 
    return newKey
 
 
def is_unlock(row, col, keyL, lockCnt, key, lock):
    """ lock[row][col] 위치에서 key를 통해 자물쇠를 열 수 있는지 확인한다. """
    cnt = 0
 
    for r in range(row, row + keyL + 1):
        for c in range(col, col + keyL + 1):
            if key[r - row][c - col] == 1 and lock[r][c] == 0:
                lock[r][c] = 1
                cnt += 1
            elif key[r - row][c - col] == 1 and lock[r][c] == 1:
                return False
 
    if cnt == lockCnt:
        return True
    else:
        return False
 
 
def solution(key, lock):
 
    lockCnt = 0
 
    for row in lock:
        lockCnt += row.count(0)
 
    newLock = set_padding(key, lock)
 
    keyL = len(key) - 1
    lockL = len(newLock)
 
    for _ in range(4):
        key = rotate_key(key)
 
        for row in range(lockL-keyL):
            for col in range(lockL-keyL):
                newLock = set_padding(key, lock)
                if is_unlock(row, col, keyL, lockCnt, key, newLock):
                    return True
    return False
 
 
def main():
 
    key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
    lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
 
    print(solution(key, lock))
 
 
if __name__ == '__main__':
    main()