[알고리즘] 자물쇠와 열쇠

*카카오 2020 신입 공채문제

 

 

문제 설명

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

 

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

 

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

 

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열 수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

 

>> 이게 말이 어려운데 예시 그림을 보면 쉽다.

저 상태에서 key를 90도 시계방향으로 회전시키고 오른쪽으로 한칸 아래로 한칸 하면 Lock에 딱 알맞게 들어간다. 따라서 출력값은 true가 된다.

 

 

사고의 흐름

1) 그러니깐 key를 요리조리 돌리고 움직여서 맞춰지는 지를 확인하면 되는 문제구나. 근데 맞출 수 없는지를 알기 위해서는 해볼 수 있는 모든 경우의 수를 전부 시도해야되니깐 완전 탐색을 해야겠다. 

 

2) 예제 key 그림을 보면 댕댕이는 Lock 외부에 위치하게 됨을 알 수 있다. 따라서 key의 돌기가 lock 자체를 벗어날 수 있겠구나라는 생각을 했고 Lock의 크기를 키워줄 필요성을 느꼈다. 2배 키워보려고 했는데 애매해서 3배 키우고 가운데에 Lock을 위치했다.

 

3) 이제 이런저런 방법을 시도해본 후에 가운데가 전부 1로 가득채워져있는지 확인하고 이때 채워져있으면 true를 반환하면 되겠다. 아마 sum() == 9 return True: 이런 느낌으로

 

4) 그러면 이제 열쇠를 이리저리 회전을 하면서 넣어볼건데 아 앞길이 막막하다...

 

 

소스코드(code)

def rotate_90(a):
    col = len(a)
    row = len(a[0])
    result = [[0]* row for _ in range(col)]
    for i in range(col):
        for j in range(row):
            result[j][row-i-1] = a[i][j]
    return result


def check(new_lock):
    lock_length = len(new_lock) // 3
    for i in range(lock_length, lock_length*2):
        for j in range(lock_length,lock_length*2):
            if new_lock[i][j] != 1:
                return False
    return True


def sol(key, lock):
    n = len(key)
    m = len(lock)

    new_lock = [[0]*(n*3) for _ in range(n*3)]

    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]
    
    for rotation in range(4):
        ket = rotate_90(key)
        for x in range(n*2):
            for y in range(n*2):
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] += ket[i][j]
                    if check(new_lock) == True:
                        return True
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] -= key[i][j]
    return False

회전함수, 검사 함수, 정답 함수 이렇게 3개의 함수를 구현하였다. 순서대로 어떤 기능을 하는 함수인지 소개하겠다.

 

1) 회전함수는 말그대로 key값을 90도 회전하는 함수이다. 가령 key의 값이 [[1,2,3],[4,5,6],[7,8,9]]라고 한다면 rotate_90(key) 함수에 들어갔다 나오면 90도 회전된 [[7,4,1],[8,5,2],[9,6,3]]이 된다. 왜 저게 90도 회전이냐라고 물어본다면 하.... 그냥 해보세요. 저도 저기서 시간을 많이 썼는데 이게 그냥 저렇게 해야 됨.

 

 

2) check 함수는 lock을 이제 3x3이었으면 9x9로 확대를 시켰잖아요. 거기서 이제 가운데 3x3 부분만을 이중 리스트로 확인한 후에 전부 1인경우의 true를 return 하고 하나라도 1이 아닌 수가 있으면 false를 return하는 함수에요. 가운데 3x3의 왼쪽 위 좌표는 (3,3)이고 오른쪽 아래 좌표는 (6,6)입니다. 따라서 왜 range가 ( lock_length, lock_length * 2 ) 인지는 아시겠죠? 

 

 

3) 정답 함수 부분을 설명하겠습니다. 이제 new_lock은 3x3을 9x9꼴로 확대를 시킨 것입니다. 확장된 잠금의 중앙에 lock을 배치하기 위해서 2중 for문과 new_lock[i+n][j+n] = lock[i][j]가 사용되었습니다. 이건 check 함수의 range를 설정해준 매커니즘과 유사합니다.

 

이후 key를 회전시켜줍니다.

 

이후 가능한 모든 key 위치를 반복합니다.

 

key값은 new_lock 위에 있는 x,y위치에 지정됩니다. 이후 new_lock 값에 key값이 더해지고 check()함수에 들어가게 됩니다. 만약 new_lock의 갑이 1인 지점에 key값인 1이 더해지면 2가 되서 return 값이 false가 되겠죠?

 

근데 만약에 만약 전부 값이 1이된다면 return True를 해주고 종료를 해줍니다.

 

또한 해당 위치에서 한번 열쇠를 넣어봤다면 다음 위치에서 열쇠를 넣어줄 때에는 현재 넣어준 열쇠의 값을 new_lock에서 빼주어야겠죠. 그 코드가 바로 밑에 나옵니다.

 

모든 경우의 수를 시도해봤는데 return True가 되지 않는다면 해당 열쇠는 잠금을 해제할 수 없는 것임으로 False를 반환합니다. 아이고 어려워