자물쇠와 열쇠

이종호·2020년 10월 12일

알고리즘

목록 보기

16/18

설명

https://programmers.co.kr/learn/courses/30/lessons/60059

풀이 계획

이것 역시 완전 탐색 방법으로 풀여야 할 것 같다.
한 조각이라도 걸치는 상태의 모든 방법을 구현해 봐야 할것이며
시간복잡도는 ((20-1) x 2 -1) x 4가 최대일 것 같다.(4회전을 하면서 키를 전부 밀어넣어보는 방법)

그럼 다시 문제는 밀어넣을 키 모양이 주어졌고, 대입해볼 자물쇠가 주어질 것이다.

이 때 밀어넣을 키 모양은 좌측 상단부터 해서 짜를 것인지,
~~Lock의 맞춰지는 크기에 따라 key를 자르는 식으로 해야할 것 같다.~~
~~아니 key를 자를 부분을 만들고 나머지를 0으로 하면,,~~
아니 M+(N-1)x2크기의 키 배열을 만들고
가운데는 key배열 그대로고 나머지는 0으로 가득 채운다.
여기서 이제
0부터 ~ len(new_key)-N까지 인덱스를 증가시키면서 만든 배열을 lock과 같은 배열인지 확인하는 식을 만들면 되지 않을까?

그리고 배열을 90도 회전시키는 로직을 구현

확인하는 방법은 lock을 돌면서 1인 인덱스에는 key는 0을, lock이 0일때는 key가 1인 걸 확인하면 된다.
여기서 한 번이라도 틀리면 바로 continue,
안틀리면 true를 리턴하면 되지않을까?

근데 위에서 모든 인덱스의 값이 반대된다를 이용한다면? python비교를 통해 할 수 도 있지 않을까 싶지만,, 일단은 그냥 2중 for문으로 해결해 보자.

다시 정리해보면

key배열을 m + (n-1)*2형태의 배열 new_key로 바꾼다.
0부터 len(new_key)-n까지 2중 for로 돌면서선택된 temp배열을 lock배열과 비교한다.
for 문을 통과하면 print(true)못하면 continue로 즉시 새로운 배열로 비교한다.
1각도에서 못 찾았으면 90도 회전한다.

90도 회전하는 방법에 대한 고찰

new_arr[i][j] = arr[m-j][i]으로 하면 될듯 싶다.

m + (n-1)*2 형태(== (n-1) + m + (n-1))의 배열을 만드는 고찰

if i>=n-1 and i<(m+n-1) and same j:
arr[i][j] = key[i-m][j-m]

결론

결국 답을 찾아 봤고, 뭔가 근처까진 갔지만 구현능력이 부족하여 도중 포기하게되었다.

다른 곳에서는 lock을 크게하여 검사하는 방법을 구현했다.
key를 크게하는 방법은 key를 돌려야하는데 더 크니까 불필요한 연산이 많아서 일 수도 있고 아니면 key를 크게하여 검사하는 방법의 구현이 더 복잡해서

아니면 key로 하는 방법은 할 수 없을지도 모른다.

오늘은 말고 좀 컨디션이 좋은 날 시도해 봐야겠다.

구현 코드


def attach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] += key[i][j]

def detach(x, y, M, key, board):
    for i in range(M):
        for j in range(M):
            board[x+i][y+j] -= key[i][j]

def rotate90(arr):
    # test = list(zip(*arr[::-1]))
    mk_arr = [[0] * len(arr) for _ in range(len(arr))]
    for i in range(len(arr)):
        for j in range(len(arr)):
            mk_arr[i][j] = arr[2-j][i]
    return mk_arr

def check(board, M, N):
    for i in range(N):
        for j in range(N):
            if board[M+i][M+j] != 1:
                return False
    return True

def solution(key, lock):
    M, N = len(key), len(lock)

    board = [[0] * (M*2 + N) for _ in range(M*2 + N)]

    #자물쇠 중앙 배치
    for i in range(N):
        for j in range(N):
            board[M+i][M+j] = lock[i][j]
    print(board)
    rotated_key = key
    # 모든 방향(4번 루프)
    for _ in range(4):
        rotated_key = rotate90(rotated_key)
        for x in range(1, M+N):
            for y in range(1, M+N):
                # 열쇠 넣어보기
                attach(x, y, M, rotated_key, board)
                # lock 가능 check
                if (check(board, M, N)):
                    return True
                # 열쇠 빼기
                detach(x, y, M, rotated_key, board)
    return False

key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
print(solution(key, lock))