2020 KAKAO BLIND RECRUITMENT

자물쇠와 열쇠.py

def solution(key, lock):
    def rotate(mat): # 90도 회전 코드
        n = len(mat)
        m = len(mat[0])
        tmp = [[0]*n for _ in range(m)]

        for i in range(n):
            for j in range(m):
                tmp[j][n-i-1] = mat[i][j]
        return tmp


    m, n = len(key), len(lock)

    # 자물쇠 공간을 넓히고, 가운데 위치에만 lock 집어넣기
    # 이중 for문으로 key-lock 대응되는 모든 케이스 계산 가능
    extend = [[-1]*(n+2*(m-1)) for _ in range(n+2*(m-1))]
    num_groove = 0
    for i in range(n):
        for j in range(n):
            extend[m-1+i][m-1+j] = lock[i][j]
            if lock[i][j] == 0: num_groove += 1

    # 90도 회전시키면서(최대 4번) 맞아떨어지는 지점 있는지 체크
    for _ in range(4):
        key = rotate(key)

        for i in range(n+m-1):
            for j in range(n+m-1):
                # (i, j): key와 lock이 만나는 부분의 좌상단 좌표
                crash_flag = False # 현재 상태에서 key와 lock 충돌이 일어나는가?
                num_match = 0 # 홈-돌기 맞는 개수
                for x in range(m):
                    for y in range(m):
                        # 현재 자물쇠와 열쇠 홈/돌기
                        cur_key = key[x][y]
                        cur_lock = extend[i+x][j+y]

                        if cur_lock == -1: continue # 실제 자물쇠 바깥, 확인 필요 X
                        # key, lock이 (0,0) 또는 (1,1)이면 안 됨
                        if cur_lock + cur_key == 1: 
                            if cur_lock == 0: # 자물쇠의 홈에 들어가는 갯수
                                    num_match += 1
                        else: #여는 것이 불가능한 경우(홈-홈, 돌기-돌기)
                            crash_flag = True
                            break
                    if crash_flag: break

                if not crash_flag and num_groove == num_match:
                    return True

    return False