[Algorithm] 자물쇠와 열쇠(feat. 2차원 리스트 회전)

최승표·2022년 2월 4일
algorithm
0

Algorithm

목록 보기
6/8


[이것이 코딩테스트다] Chapter12. Q10 자물쇠와 열쇠
문제풀러 가기

본 포스팅의 해설과 코드는 '이것이 코딩테스트다' 책의 문제와 해설을 보고 본인의 방식으로 풀어쓴 것입니다.

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

잠겨있는 자물쇠는 격자 한 칸의 크기가 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은 돌기 부분을 나타냅니다.

입출력 예
key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
result = True

입출력 예 설명
key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.



Problem Solving

 key와 lock의 최대 크기가 20이므로 열쇠를 회전하고 이동하여 자물쇠에 끼워볼 수 있는 모든 경우의 수를 알아보는 완전 탐색을 이용해서 문제를 해결할 수 있다. Image Processing에서 사용되는 convolution 연산 방법을 생각하면 탐색이 쉬워진다. lock을 Input Image로 key를 Mask로 생각하여 문제를 해결해보자.

  1. 먼저 lock에 zero padding을 추가한다.

  2. stride = 1로 mask를 옮겨가며 홈과 돌기가 맞는지 확인한다.

  3. key를 회전한 후 1번을 반복한다.



Python Code

def rotate_key(a):
    n = len(a)
    m = len(a[0])
    res = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            res[j][n-1-i] = a[i][j]
    return res

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

def solution(key, lock):
    n = len(key)
    m = len(lock)
    pad_lock = [[0]*(n*3) for _ in range(n*3)]
    for i in range(n):
        for j in range(n):
            pad_lock[i+n][j+n] = lock[i][j]
    
    for rotation in range(4):
        key = rotate_key(key)
        for x in range(n*2):
            for y in range(n*2):
                for i in range(m):
                    for j in range(m):
                        pad_lock[x+i][y+i] += lock[i][j]
                if is_lock(pad_lock):
                    return True
                for i in range(m):
                    for j in range(m):
                        pad_lock[x+i][y+i] -= lock[i][j]
    return False
  • 2차원 배열의 회전
  • 인덱스의 접근에 용이하게 lock의 크기를 3배로 늘려버리고 가운데에가 기존의 lock을 삽입



Discussion

  • 문제를 보자마자 Convoluton 연산 방법을 활용해서 완전 탐색을 진행하면 풀이 가능할 거라고 생각
  • Python은 1초 안에 2천만 정도 연산이 가능함을 인지하게 됌.

My solution

def is_unlock(m,n,tmp):
    for i in range(n):
        for j in range(n):
            if tmp[i+m-1][j+m-1]==0:
                return False
    return True

def key_rotated(array_2d):
    list_of_tuples = zip(*array_2d[::-1])
    return [list(elem) for elem in list_of_tuples]

def solution(key, lock):
    m = len(key)
    n = len(lock)
    pad=n+2*(m-1)
    zero_padding = [[0]* pad for _ in range(pad)]
    for i in range(n):
        for j in range(n):
            zero_padding[i+m-1][j+m-1] = lock[i][j]
    
    # 2차원 리스트의 깊은 복사
    tmp = [item[:] for item in zero_padding] 

    # 4 방향에 대해 확인
    for _ in range(4):
        for k in range(pad-m+1):
            for y in range(pad-m+1):
                for i in range(k,k+m):
                    for j in range(y,y+m):
                        if zero_padding[i][j]==0 and key[i-k][j-y]==1:
                            tmp[i][j]=1
                        elif zero_padding[i][j]==1 and key[i-k][j-y]==1:
                            tmp[i][j]=0
                if is_unlock(m,n,tmp):
                    return True
                tmp = [item[:] for item in zero_padding]
        key = key_rotated(key)
    return False
  • 쓰이는 부분만 패딩을 적용.
  • 초기 lock을 저장해두고 판별할때마다 초기화하는 방식으로 진행.
  • 그 과정에서 2차원 리스트의 복사에 대해 공부


얕은 복사 / 깊은 복사

  • 리스트는 id값으로 접근하기에 복사하려면 아래의 방법을 사용해야한다.

    • copy_list = li id()함수로 두 함수의 주소값을 확인하면 같은 값이다.
    • copy_list = li.copy()
    • copy_list = list(li)
    • copy_list = li[:]
    • copy_list = [] + li

  • 하지만 2차원 이상 리스트는 위의 방법으로도 주소값이 복사되어 값을 유지할 수 없다. 따라서 아래 방법 중 하나를 이용해 값을 복사할 수 있다.

    • copy 모듈의 deepcopy 함수를 사용하는 방법이다. 이 방법은 속도가 느리기에 코딩테스트에 적합하지 않을 수 있다.
      from copy import deepcopy
copy_list = deepcopy(li)
    • copy_list = [item[:] for item in li]

  • 참고 사이트


pack / unpack

  • list / tuple 에서는 *, dict에서는 **를 사용해서 요소를 pack / unpack 할 수 있다.

  • *을 붙인 매개변수에 하나 혹은 여러개의 객체가 들어올 경우 해당 객체들은 pack 되어 저장된다.

def test_pack(*num):
  print(num)
test_pack(5, 6, 7)
# 결과 : (5, 6, 7)
  • 여러개의 객체를 * 를 붙여서 매개변수로 전달하면 해당 객체들은 unpack 되어 저장된다.
def test_unpack(a, b, c, d):
  print(a, b, c, d)
li = [5,6,7,8]
test_unpack(*li)
# 결과 : 5 6 7 8
  • 2차원 리스트 출력
li = [[i*3+j for j in range(3)] for i in range(3)]
for item in li:
	print(*item)
# 결과
0 1 2
3 4 5
6 7 8

zip

  • zip(*iterable) 은 동일한 개수로 이루어진 iterable 자료형을 묶어준다.
li = [[0,1],[2,3]]
print(list(zip(*testList)))
# 결과 : [(0, 2), (1, 3)]
  • 2차원 리스트를 먼저 reverse하고 unpack해서 zip하면 각 열이 묶이게 되어서 오른쪽으로 90도 회전한 것이 된다.
li = [[i*3+j for j in range(3)] for i in range(3)]
li = list(zip(*li[::-1]))
for item in li:
	print(*item)
# 결과
6 3 0
7 4 1
8 5 2

References

profile
최승표
"계속해서, 될 때까지" AI Engineer
이전 포스트

[Algorithm] 문자열 압축

다음 포스트

[Algorithm] 뱀

0개의 댓글