[프로그래머스] Lv3. 자물쇠와 열쇠 (2020 카카오 공채)

🔗

풀이

열쇠로 자물쇠의 모든 홈을 채울 수 있는가를 묻는 문제이다. 반드시 모든 홈을 채워야 하는데 그게 열쇠의 모든 돌기 부분을 사용하지 않을 수도 있다. 이 부분을 오해해서 한참을 헤맸다. 반대로 열쇠의 모든 돌기를 사용했더라도 자물쇠의 홈이 하나라도 채워지지 않았다면 False를 반환해야 한다.

자물쇠와 열쇠의 배열 모두 최대 크기가 20x20이기 때문에 완전탐색으로 한 칸씩 확인해도 가능할 것 같았다. 자물쇠와 열쇠의 돌기 부분이 겹치면 안 되기 때문에 만약 겹칠 경우 도중에 탐색을 중단하는 백트래킹으로 구현했다. 열쇠의 모든 홈이 채워지는 경우에만 True를 반환할 수 있도록 했다. 기본적으로 열쇠를 자물쇠의 (0, 0)칸부터 한칸씨 오른쪽 아래로 옮겨가면서 비교할 수 있도록 했다. 탐색 도중에 일치하는 부분이 나온다면 바로 True를 반환하며 함수를 종료했다.

def rotate(arr):
    return list(map(list, zip(*arr[::-1])))

def solution(key, lock):
    m, n = len(key), len(lock)
    hole = sum(n-sum(row) for row in lock)
    
    # 자물쇠에 처음부터 빈 홈이 없는 경우
    if not hole:
        return True
    
    # 열쇠를 4번 회전한 값 미리 저장
    rotate_arr = [key]
    for i in range(3):
        rotate_arr.append(rotate(rotate_arr[i]))
    
    # 열쇠가 자물쇠의 모든 홈을 채울 수 있는지 확인
    def match(i, j, key, hole):
        for ki in range(m):
            for kj in range(m):
                li, lj = i+ki, j+kj
                if not (-1<li<n and -1<lj<n):
                    continue
                
                # 열쇠와 자물쇠의 돌기가 겹치는 경우
                if key[ki][kj] and lock[li][lj]:
                    return False
                
                # 열쇠가 자물쇠의 홈을 채울 수 있는 경우
                if key[ki][kj] and not lock[li][lj]:
                    hole -= 1
        return not hole
    
    for i in range(-m+1, n):
        for j in range(-m+1, n):
            for k in range(4):
                if match(i, j, rotate_arr[k], hole):
                    return True
    return False