★자물쇠와 열쇠★

★다시 풀어봐야할 문제★ (나중에 최적화 해보기)

과거 기록(이전에 풀려했는데 구현 너무 복잡하고 짜증나서 결국 못풀었음 → 재도전 성공!)

'''
아이디어
열쇠를 중심부로부터 k 만큼 떨어뜨리고 한바퀴 돌리는 함수 (key와 lock이 각각 홀홀,짝짝,홀짝,짝홀 인경우가 있을 수 있음)

홀홀 일때는 중심에 놓고 시작 k=0 ~ k=까지

열쇠를 시계방향으로 회전시키는 함수

시간복잡도
1600*1600 = 2,560,000 
완탐 가능

자료구조
전체 배열 M+N+M * 2
자물쇠 꽉채워져야하는 영역 M ~ M+N-1 *2
'''

def solution(key, lock):
    answer = True
    M = len(key)
    N = len(lock)
    big_matrix = [[0 for _ in range(M*2+N)] for _ in range(M*2+N)]
    print(big_matrix)
    
    return answer

접근 방법 [필수 작성]

제한사항

• 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은 돌기 부분을 나타냅니다.

아이디어

제한사항 굉장히 숫자가 작은걸로 봐서는 완전탐색 가능하지 않을까로 접근

모든 경우에 대해서 돌려보고 슬라이드 해보면서 각 pixel 을 더해보고

lock 의 범위에 대해서 2가 되거나 0이 되는 부분이 있으면 재귀함수를 빠져나오고 다음 루프 실행

만약 모든 lock 의 범위가 1이 되면, result 를 True 로 리턴

[열쇠랑 자물쇠 비교판 만들기 아이디어]

→ 비교판의 총 크기는 (2M+N-2) X (2M+N-2)

그 중 자물쇠 영역은 M-1 ~ M+N-2 까지 → 이 사이 영역의 모든 수가 1인지를 확인하면 됨 → 하나라도 1이 아니면 바로 탈락 후 다음거 진행

add_on_board() 를 활용해서 자물쇠를 비교판위에 추가한 후, add_on_board() 를 열쇠에 대해서 가로세로 모두 0~M+N-2 까지 재귀적으로 실행

[열쇠 회전 아이디어]

각 픽셀별로 x,y 변화값에 특징이 있음.

key 가로세로 길이가 M 이라 하면 M-1 이 최대 변화량인데, 아래 그림과 같은 특징을 가짐

시간복잡도

한번 위에서 아래로, 또는 왼쪽에서 오른쪽으로 슬라이드 하는데 걸리는 횟수 → M+N-1

자물쇠랑 열쇠랑 맞는지 확인하기 → 최대 M*M번

열쇠 돌리는 가짓수 → 4번

전체 완전탐색에 소요되는 연산횟수 → (M+N-1)^2M^24 → O((M+N)^2M^2) → O(M^4+2M^3N+M^2*N^2) → M의 최댓값과 N의 최댓값이 같음 → O(M^4) → 20^4 = 16만 << 1억 → 완전탐색으로 풀 수 있겠네!

자료구조 및 함수

add_key_and_check(start_y,start_x,board) → 비교판 위에 넣고 체크하는 함수

def rotate_key(key): → 열쇠를 시계방향으로 한바퀴 돌리는 함수

코드 구현 [필수 작성]

오류코드 (15분 고민해봐도 Corner Case 를 찾지 못했음)

# 7시40분 시작 -> 9시5분 중간점검 -> 9시20분 잘못된 부분 찾을수가 없음

def solution(key, lock):
    M = len(key)
    N = len(lock)
    lock_board = [[0]*(2*M+N-2) for _ in range(2*M+N-2)]
    
    #자물쇠 정보를 lock_board 에 추가
    for y in range(N):
        for x in range(N):
            lock_board[M-1+y][M-1+x] += lock[y][x]
            
    # # lock_board test
    # for y in range(len(lock_board)):
    #     print(lock_board[y])
    def print_matrix(matrix):
        for y in range(len(matrix)):
            print(matrix[y])
        
    def rotate_key(key):
        M = len(key)
        rotated_key = [[0]*(M) for _ in range(M)]
        for dr in range(M): #dr means deference of row
            for dc in range(M): #dc means deference of column
                rotated_key[dr][dc] = key[M-1-dc][dr]
        return rotated_key
    
    # #rotate_key test
    # #가로세로가 짝수인 경우
    # key = [[0, 0, 0, 0], [1, 1, 0, 0], [1, 0, 1, 1],[0, 0, 0, 1]]
    # for y in range(len(key)):
    #     print(key[y])
    # key = rotate_key(key)
    # print("-------------")
    # for y in range(len(key)):
    #     print(key[y])
    
    def add_key_and_check(start_y, start_x, key, board):
        nonlocal N
        
        for y in range(M):
            for x in range(M):
                if M-1 <= start_y+y <= M+N-2 and M-1 <= start_x+x <= M+N-2:
                    if (board[start_y+y][start_x+x] + key[y][x]) != 1:
                        return False
        return True
    
    # #add_key_and_check test
    # print(add_key_and_check(0, 0, key, lock_board))
    # print(add_key_and_check(3, 3, rotate_key(key), lock_board))
    
    for i in range(4):
        key = rotate_key(key)
        for y in range(M+N-1):
            for x in range(M+N-1):
                if add_key_and_check(y, x, key, lock_board):
                    return True
    return False

수정코드

# 7시40분 시작 -> 9시5분 중간점검 -> 9시15분 잘못된 부분 찾을수가 없음

def solution(key, lock):
    M = len(key)
    N = len(lock)
    lock_board = [[0]*(2*M+N-2) for _ in range(2*M+N-2)]
    
    def init_lock_board():
        nonlocal lock_board
        nonlocal lock
        
        lock_board = [[0]*(2*M+N-2) for _ in range(2*M+N-2)]
        #자물쇠 정보를 lock_board 에 추가
        for y in range(N):
            for x in range(N):
                lock_board[M-1+y][M-1+x] += lock[y][x]
            
    # # lock_board test
    # for y in range(len(lock_board)):
    #     print(lock_board[y])
    def print_matrix(matrix):
        for y in range(len(matrix)):
            print(matrix[y])
        
    def rotate_key(key):
        M = len(key)
        rotated_key = [[0]*(M) for _ in range(M)]
        for dr in range(M): #dr means deference of row
            for dc in range(M): #dc means deference of column
                rotated_key[dr][dc] = key[M-1-dc][dr]
        return rotated_key
    
    # #rotate_key test
    # #가로세로가 짝수인 경우
    # key = [[0, 0, 0, 0], [1, 1, 0, 0], [1, 0, 1, 1],[0, 0, 0, 1]]
    # for y in range(len(key)):
    #     print(key[y])
    # key = rotate_key(key)
    # print("-------------")
    # for y in range(len(key)):
    #     print(key[y])
    
    def add_key_and_check(start_y, start_x, key, board):
        nonlocal N
        
        for y in range(M):
            for x in range(M):
                if M-1 <= start_y+y <= M+N-2 and M-1 <= start_x+x <= M+N-2:
                    board[start_y+y][start_x+x] += key[y][x]
                    if board[start_y+y][start_x+x] != 1:
                        return False
        for y in range(N):
            for x in range(N):
                if board[M-1+y][M-1+x] != 1:
                    return False
        return True
    
    # #add_key_and_check test
    # print(add_key_and_check(0, 0, key, lock_board))
    # print(add_key_and_check(3, 3, rotate_key(key), lock_board))
    
    for i in range(4):
        key = rotate_key(key)
        for y in range(M+N-1):
            for x in range(M+N-1):
                if add_key_and_check(y, x, key, lock_board):
                    return True
                init_lock_board()
    return False

반례:

key = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
lock = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
return = False

corner case 핵심 → 열쇠가 자물쇠랑 맞는지만 체크하는 것이 아닌, 모든 자물쇠의 빈 영역이 채워졌는지까지 확인해야한다.

배우게 된 점 [ 필수 X ]

자유 형식

질문 [ 필수 X ]

Q1

코드의 잘못된 부분 찾을수가 없음

→ unit test 를 통해 user_defined 함수가 모두 의도한 대로 작동하는 것으로 보이고,

main 함수부분에서 반복문을 활용한 완전탐색을 시도하였으나, 만점을 받지 못하는 상황

어떠한 corner case 가 있는지 모르겠습니다….

해설코드와도 비교해보았는데, 약간 index 계산법이 다른것 같은데 index 계산을 제가 잘못한건지..

(index 계산을 잘못했다면 부분점수도 못받았을 거라고 생각합니다.)

뭐가 문제인지 잘 모르겠습니다.

피드백 [ 코치 작성 ]

화이팅입니다!

반례:

key = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
lock = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
return = False