문제

->링크 <-

해결 방법

먼저 해결 예시에 보여줬던 것처럼
열쇠를 90도로 회전시키고 상하좌우로 이동시키고
각 이동 회전된 KEY값에 대해서 자물쇠와 덧셈을 해준다.
이 때 더해준 2차원 리스트 값이 모두 1이 나온다면 True를 리턴해주면 된다.

따라서 3겹의 반복문으로 이루어진다.

1.각 90도씩 총 4번 회전 시키는 반복문(회전 안하는 것도 포함)
2.회전되있는 열쇠를 상하좌우로 이동시켜본다
3.이렇게 열쇠가 움직여본 후 lock의 모든 부분과 더해준다.

3번이 약간 이해가 안갈 수 있는데
예를 들어 22 열쇠가 있고 33자물쇠가 있다면 4번의 더해줄 수 있는
모든 경우를 각각 더해보고 더해진 리스트가 모두 1이 되는지 확인해본다.

time error

이 해결 방법으로 구현해본 코드는 밑에 있는데 역시
time error가 나왔다ㅠㅠㅠ

import copy

def solution(key, lock):
    answer = False
    
    N = len(lock[0])
    M = len(key[0])
    
    
    #열쇠를 90도씩 돌려보는 반복문
    for i in range(4):
        #최초 i가 0일 때는 회전 X
        if i > 0:
            tmp = [[0] * M for i in range(M)]
            
            for i in range(M):
                for j in range(M):
                    tmp[i][j] = key[j][M-1-i]
            key = copy.deepcopy(tmp)
        
        #열쇠를 상하좌우 움직여보는 반복문
        for ud in range(-M+1, M):
            for lr in range(-M+1, M):
                tmp = [[0] * M for _ in range(M)]
                #위로 움직여야 할 때
                if ud < 0:
                    for i in range(M):
                        for j in range(M):
                            #0으로 채워야 할 때
                            if(i > M-1 + ud):
                                tmp[i][j] = 0
                            #이동을 해줘야 할 때
                            else:
                                tmp[i][j] = key[i-ud][j]
                            
                #아래로 움직여야 할 때
                else:
                    for i in range(M):
                        for j in range(M):
                            #0으로 채워야 할 때
                            if(i < ud):
                                tmp[i][j] = 0
                            #이동을 해줘야 할 때
                            else:
                                tmp[i][j] = key[i-ud][j]
                #왼쪽으로 움직여야 할 때
                if lr < 0:
                    for i in range(M):
                        for j in range(M):
                            #0으로 채워야 할 때
                            if(j > M-1 + lr):
                                tmp[i][j] = 0
                            #이동을 해줘야 할 때
                            else:
                                tmp[i][j] = tmp[i][j-lr]
                #오른쪽으 로 움직여야 할 때
                else:
                    for i in range(M):
                        for j in range(M):
                            #0으로 채워야 할 때
                            if(j > lr):
                                tmp[i][j] = 0
                            #이동을 해줘야 할 때
                            else:
                                tmp[i][j] = tmp[i][j-lr]
                #최종적으로 자물쇠에 맞춰봐야하는 key
                key = copy.deepcopy(tmp)
                
                #자물쇠에 맞춰보는 반복문
                tmp = copy.deepcopy(lock)
                i = 0
                j = 0
                y = 0
                x = 0
                while i + y <= M-1:
                    while j + x <= M-1:
                        while i < M:
                            while j < M:
                                tmp[i+y][j+x] = key[i][j] + lock[i+y][j+x]
                                #자물쇠가 모두 1인지 확인
                                flag = True
                                for a in range(N):
                                    for b in range(N):
                                        if lock[a][b] == 0:
                                            flag = False
                                if flag == True:
                                    return True
                        j+=1
                    j = 0
                    i += 1

    return answer

새로운 해결방법

정답을 서칭해보고 알게된 해결방법인데 사실 이게더 직관적이고 더 좋은 방법인거 같다. 근데 나는 왜 이방법이 안 떠올랐을까ㅠㅠㅠ

이 해결방법의 핵심은 바로 새로운 N+2*M의 크기의 정사각형 리스트를 새로만들어 이공간에서 열쇠와 자물쇠를 맞춰보는 것이다.

기존의 방법은 열쇠를 옮겨주고 또 거기서 자물쇠 내에서 옮겨주며 더하니 새로운방법에서 할 연산을 두번씩이나 해줬던 것이다!!!
이렇게 하니 훨씬 쉽고 시간도 짧게 걸렸다.

새로운 코드

#회전시킨 열쇠를 리턴해주는 함수
def roll(key):
    size = len(key[0])
    tmp = [[0] * size for _ in range(size)]
    for i in range(size):
        for j in range(size):
            tmp[i][j] = key[size-1-j][i]
    return tmp
            
#자물쇠가 열리는지 안열리는지 확인해주는 함수
def correct(test, N, M):
    for i in range(M, M+N):
        for j in range(M, M+N):
            if test[i][j] != 1:
                return False
    return True
    
def solution(key, lock):
    answer = True
    
    N = len(lock[0])
    M = len(key[0])
    size = N + 2*M
    
    for i in range(4):
        key = roll(key)
        #lock을 이동하며 더하기 i와 j는 테스트 공간안에서 더할 key의 시작지점을 의미
        for i in range(N+M+1):
            for j in range(N+M+1):
                #새로운 공간 만들어 주기
                test = [[0] * size for _ in range(size)]
                for a in range(N):
                    for b in range(N):
                        test[M+a][M+b] = lock[a][b]
                
                #이동시킨 key로 새로운 공간에 더해주기
                for a in range(M):
                    for b in range(M):
                        test[i+a][j+b] = key[a][b] + test[i+a][j+b]
                #더해준게 열리는지 확인
                if correct(test, N, M) == True:
                    return True

    return False