자물쇠와 열쇠

문제 설명

https://programmers.co.kr/learn/courses/30/lessons/60059
각각 N*N, M*M의 각 원소가 0과 1로만 이루어진 2차원 배열 형태로 자물쇠(lock)과 열쇠(key)의 정보가 주어질 때, 열쇠로 자물쇠를 열 수 있는 지 판단하라. 자물쇠가 0 인 부분에 열쇠가 1인 부분이 딱 맞아야 한다. 열쇠를 회전시키든 상하좌우로 한 칸 씩 이동시키든 상관없다.

<입력>
key는 M*M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열
lock은 N*N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열
M <= N
key와 lock의 원소는 0 또는 1
0은 홈 부분, 1은 돌기 부분

<출력>
bool

<예시>
key
[[0, 0, 0],
[1, 0, 0],
[0, 1, 1]]

lock
[[1, 1, 1],
[1, 1, 0],
[1, 0, 1]]

True

---

나의 풀이 -> (실패)

90도 회전 함수, 상하좌우 각각 이동함수를 다 작성한 다음
모든 경우의 수를 완전탐색하면 되지 않을까? 그런데 어떻게..??

def rotate_90(key):
    num = len(key) # 3
    new_key = [[0] * num for _ in range(num)] # 깊은 복사
    for i in range(num):
        for j in range(num):
            new_key[j][num-1-i] = key[i][j]
    return new_key

def move_right(key):
    num = len(key) # 3
    new_key = [[0] * num for _ in range(num)]
    for i in range(num):
        for j in range(num):
            if j == 0:
                new_key[i][j] = 0
            else:
                new_key[i][j] = key[i][j-1]
    return new_key

def move_left(key):
    num = len(key) # 3
    new_key = [[0] * num for _ in range(num)]
    for i in range(num):
        for j in range(num):
            if j == 2:
                new_key[i][j] = 0
            else:
                new_key[i][j] = key[i][j+1]
    return new_key

def move_up(key):
    num = len(key) # 3
    new_key = [[0] * num for _ in range(num)]
    for i in range(num):
        for j in range(num):
            if i == 2:
                new_key[i][j] = 0
            else:
                new_key[i][j] = key[i+1][j]
    return new_key

def move_down(key):
    num = len(key) # 3
    new_key = [[0] * num for _ in range(num)]
    for i in range(num):
        for j in range(num):
            if i == 0:
                new_key[i][j] = 0
            else:
                new_key[i][j] = key[i-1][j]
    return new_key

...

---

책 풀이

완전 탐색을 위해 자물쇠를 확장시킨다. 3*3 배열이라면 길이를 3배로 늘린 새로운 배열을 선언한 후 자물쇠 정보를 중앙에 배치시킨다. 그리고 열쇠를 이동시키면서 자물쇠가 전부 1이 되는 지 판단한다. 2가 되거나 0이 남은 경우는 false를 반환하게끔. 회전 시켜서 앞에 거 반복.

def rotate_90(key):
    num = len(key)
    new_key = [[0] * num for _ in range(num)]

    for i in range(num):
        for j in range(num):
            new_key[j][num-1-i] = key[i][j]
    return new_key

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 solution(key, lock):
    n = len(lock)
    m = len(key)

    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):
        key = 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] += key [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

---

느낀 점

문제 뒤졌다 좀 이따 보자 쉬운 문제 먼저 풀고 온다