On.

---

Algorithm

---

1. 수도코드

0) 문제 유형 파악: 완전 탐색 문제

1) M과 N이 겹치는 최대 사이즈 board 생성

• 문제에서 key와 lock의 길이 M, N이 많이 사용되므로 변수로 선언

2) board 중심에 lock값 배치

3) (90도, 180도, 270도, 360도) 회전시킨 key 전부를 board에 대조시켜 봐야하기 때문에 board와 lock을 겹치기 (for문)

4) board의 가로, 세로 1부터 M+N까지의 범위를 돌며 key와 lock을 겹치기 (이중 for문)

5) attach 함수로 key와 board에 겹친 영역을 더하기

6) check 함수로 lock 부분 영역이 1로 가득 찼는지 확인

• 찼으면 return True

7) detach 함수로 key와 board에 겹친 영역 빼기

• check를 했는데 key와 lock이 맞지 않는다면 lock에서 key를 더한 값을 빼줘야 한다.

8) 이중 for문이 끝났는데도 True가 나오지 않았다는 것은 키가 자물쇠와 맞지 않는다는 의미로 False를 리턴한다.

2. 구현코드

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

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

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]
    
    rotated_key = key
    for _ in range(4):
        rotated_key = rotate(rotated_key)
        for y in range(1, M+N):
            for x in range(1, M+N):
                attach((y,x), M, board, rotated_key)
                if check(M, N, board):
                    return True
                detach((y,x), M, board, rotated_key)
                
    return False

3. 배운점

• 2차원 배열을 시계방향 90도 돌리는 방법 : list( zip( *배열[::-1] ) )

• 문제 풀 때는 문제의 유형을 가장 먼저 파악해보자

---

Off.

---

프론트와 백을 넘나드는 리드 개발자가 되는 그날까지 🔥🔥🔥