[프로그래머스 / python / Level 3] 자물쇠와 열쇠

문제

 

2020 KAKAO BLIND RECRUITMENT에 출제된 문제이다.

구현, 완전탐색 문제이며 보드 확장 아이디어를 떠올리지 못한다면 풀기 까다로울 수 있는 문제이다.

 

def solution(key, lock):
    
    """
    90도 회전시키는 함수
    자물쇠가 열리는지 확인하는 함수 -> 열쇠를 보드에 적용 + 자물쇠값 모두 1인지 확인 + 열쇠를 보드에서 제거
    
    확장된 보드를 만든다
    자물쇠를 보드 중앙에 배치한다
    열쇠를 4방향으로 회전시키며, 모든 가능한 위치에서 열기 시도한다
    """
    
    """키를 시계 방향으로 90도 회전하는 함수"""
    def rotate_key(key):
        return [list(row) for row in zip(*key[::-1])]
    
    """자물쇠 해제를 시도하는 함수"""
    def try_unlock(x, y, M, N, key, board):
        
        # key를 board에 전부 더하기
        for i in range(M):
            for j in range(M):
                board[x + i][y + j] += key[i][j]
        
        # 모든 자물쇠 값이 1인지 확인
        is_unlocked = True
        for i in range(N):
            for j in range(N):
                if board[M + i][M + j] != 1:
                    is_unlocked = False
                    break
            if is_unlocked == False:
                break
        
        # 자물쇠 원상복구
        for i in range(M):
            for j in range(M):
                board[x + i][y + j] -= key[i][j]
        
        return is_unlocked
    
    """확장된 보드 만들기"""
    M = len(key)
    N = len(lock)
    board_size = M + N + M
    board = [[0] * board_size for _ in range(board_size)]
    
    """자물쇠를 보드 중앙에 배치"""
    for i in range(N):
        for j in range(N):
            board[M + i][M + j] = lock[i][j]
    
    """메인 로직, 모든 위치에 대하여 열기 시도 * 4방향"""
    current_key = key
    for _ in range(4):
        
        for x in range(M + N):
            for y in range(M + N):
                if try_unlock(x, y, M, N, current_key, board):
                    return True
                
        current_key = rotate_key(current_key)
    
    return False

 

lock과 key의 크기가 최대 20 * 20으로써, 완전탐색으로 충분히 풀 수 있다. 그러나 어떻게 해야 방향이 변하고 움직이는 열쇠를 자물쇠에 맞게 대입해 볼 수 있는지, 즉 어떻게 해야 모든 경우의 수를 만들 수 있고, 그걸 어떻게 대입하는지에 대한 아이디어가 잘 떠오르지 않았다.

 

핵심은 "확장된 보드"이다. (M + N + M) * (M + N + M) 크기의 2차원 배열로 보드를 확장해 준다. 그리고 가운데에 N * N 자물쇠를 두고, 그 주변을 전부 M * M 열쇠 크기로 꽉 채운다.
예를 들어 N = 3, M = 3 일 경우 아래와 같은 모양이 된다.

 

확장된 보드

 

이렇게 보드를 확장하고 자물쇠를 보드 가운데 배치하면, 열쇠가 자물쇠 밖으로 빠져나간 상태로 일부만 자물쇠에 걸쳐있는 상태를 구현할 수 있다. 그렇게 자물쇠와 조금이라도 겹치는 모든 경우의 수를 전부 체크해 주면 된다. 이 아이디어만 생각해 낸다면, 나머지 구현은 그렇게까지 복잡하지 않다.

 

이제 모든 경우의 수를 검사하기만 하면 되는데, 자물쇠와 겹치는 모든 경우의 수는 아래와 같이 정의할 수 있다.

    """모든 위치에 대하여 열기 시도, 4방향 반복"""
    current_key = key
    for _ in range(4):
        
        for x in range(M + N):
            for y in range(M + N):
    
    # 키 90도 회전
    rotate_key(current_key)

 

열쇠의 가장 왼쪽 위 칸을 기준점으로 잡는다. 즉 (x, y)좌표가 현재 열쇠의 가장 왼쪽 위 칸이 되는 것이다.

2중 for문의 기준이 M + N인 이유는, 해당 좌표를 넘어가는 순간 이후의 모든 좌표는 자물쇠와 전혀 겹치지 않기 때문이다.

이렇게 반복문을 진행하며 key값을 board에 전부 더해주고, 가운데 lock 위치에 있는 값만을 검사하여 모두 1인지 체크해 주면 된다. 검사한 후엔 다음 검사를 위해 board를 원상복구 해 주어야 한다.