[프로그래머스/카카오 블라인드 테스트 2020/python] 자물쇠와 열쇠

로직

완전탐색으로 열쇠와 자물쇠가 한 칸이라도 겹치는 경우의 수가 있다면 모두 체크해주는 것이다.

 

예를 들어 lock과 key 모두 3 X 3인경우,

key가 lock 주위 혹은 위를 모두 탐색하면서 키와 겹치는 부분들을 체크한다.

 

이때 고려해주어야할 파트는 크게 두 가지가 있다.

 

lock - key (key와 겹치지 않는 lock 영역)

현재 key와 겹치지 않는 lock의 영역 중 하나라도 0이 있다면 자물쇠는 열릴 수 없으므로 False 이다.

그렇기 때문에 zero_count라는 변수를 두어 lock에 남아있는 0들을 세어준다.

 

👉 골드가 말해주지 못했다면 한참 고민했을거다. 문제를 잘 읽자 제발!!

key ⋂ lock (key와 lock이 겹치는 영역)

만약 key와 lock이 겹치는 부분 값의 합이 1
→ 그 중 key가 1인 경우는 lock의 0부분을 매꿔주는 경우이므로 zero_count-- 해준다.

그렇지 않을 경우는 무조건 False다.

 

이렇게 키(key)가 모든 탐색을 끝냈는데도 자물쇠(lock)를 풀지 못했다면,

key를 90도 회전시켜주고 다시 탐색한다.

key의 (0,0) 부분이 움직이는 범위

 

코드

def solution(key, lock):
    # Brute Force Searching
    answer = True
    zero_count = count_zero_in_lock(lock)

    if zero_count == 0: return True

    for i in range(4):
        if brute_force(lock, key, zero_count): return True
        key = rotate(key)
    return False

def brute_force(lock, key, zero_count):
    N, M = len(lock), len(key)
    start = -M + 1
    end = N
    # key의 (0,0) 지점은 -M + 1 부터 N 까지 탐색한다
    for x in range(start, end):
        for y in range(start, end):
            if check(x, y, key, lock, zero_count): return True
    return False

def check(start_x, start_y, key, lock, zero_count):
    N, M = len(lock), len(key)

    # key_x, key_y : key의 절대적 인덱스
    # x + start_x, y + start_y : lock을 기준으로 했을 때 key의 상대적 인덱스
    # => 현재 키의 모든 격자를 돌면서 자물쇠와 맞물리는 곳 탐색
    for key_x in range(M):
        for key_y in range(M):
            # 인덱스 x와 y가 모두 자물쇠와 맞물린다면
            lock_x = key_x + start_x
            lock_y = key_y + start_y
            if (0 <= lock_x < N) and (0 <= lock_y < N):
                # 채워넣기 실패한 경우 바로 fasle
                if key[key_y][key_x] + lock[lock_y][lock_x] != 1:
                    return False
                # 채워넣을 경우 lock의 zero 갯수 감소
                elif key[key_y][key_x] == 1:
                    zero_count -= 1

    # 만약 lock의 모든 홈이 채워졌다면 True
    return (zero_count == 0)

def rotate(key):
    return list(zip(*key[::-1]))

def count_zero_in_lock(lock):
    return sum([row.count(0) for row in lock])

클린코드 4장 주석파트를 읽은지 매우 최근이지만.. 알고리즘에 한해서는 클린 코드를 생각하지 않기로 했다.