[프로그래머스] 자물쇠와 열쇠 (파이썬)

https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

---

열쇠 돌기 중 하나를 기준으로 하여 다른 돌기까지의 위치 변화를 리스트에 담아둡니다. 자물쇠의 홈 중 하나에 방금 기준으로 정한 열쇠 돌기를 넣고, 위치 변화에 대한 정보를 보고 다른 돌기를 전개합니다(현재 위치와 연결된 다른 돌기를 확인합니다). 그 과정에서 자물쇠의 돌기를 만난다면 중단합니다. 중단되지 않았다면, 자물쇠를 열쇠로 풀 수 있습니다.

 

* solution

    - 열쇠의 돌기 개수를 계산합니다.

    - 자물쇠의 홈 개수를 계산합니다.

    - 자물쇠의 홈 개수가 열쇠의 돌기 개수보다 많다면 풀 수 없기 때문에 False를 반환합니다.

    - 자물쇠에 홈이 없다면, 이미 열려있는 상태로 생각하여 True를 반환합니다.

 

    - 자물쇠에 있는 홈들의 좌표 정보와 위치 변화 정보를 저장합니다.

    - 열쇠에 있는 돌기들의 좌표 정보를 저장합니다.

    - 4번의 회전에 대해 확인합니다.

        - 시작점이 되는 돌기들을 바꿔가며 확인합니다.

            - 자물쇠의 위치 변화 정보와 열쇠의 위치 변화 정보가 같다면 True를 반환합니다.

            - 자물쇠의 위치 변화 정보와 열쇠의 위치 변화 정보가 몇 개 같은가를 확인합니다.

            - 자물쇠 홈 중 첫번째를 기준으로 열쇠를 전개합니다.

            - 열쇠를 전개하던 중, 자물쇠의 돌기를 만난다면 break를 발생시킵니다.

            - break가 발생하지 않았다면 True를 반환합니다. (열쇠가 자물쇠의 돌기를 만나지 않은 경우)

         - 열쇠를 회전시킵니다.

 

* get_location

    - 리스트에서 0 또는 1인 원소의 좌표를 리스트 location 에 저장합니다.

 

* get_relation

   - 하나의 좌표를 기준으로, 다른 좌표와의 위치 관계를 리스트 relation 에 저장합니다.

def solution(key, lock):
    N = len(lock)
    # M = len(key)
    key_ones = sum([sum(x) for x in key])
    lock_zeros = N**2 - sum([sum(x) for x in lock])

    if lock_zeros > key_ones:
        return False
    if not lock_zeros:
        return True

    lock_loc = get_location(lock, target=0)
    lock_rel = get_relation(lock_loc, 0)
    for _ in range(4):
        key_loc = get_location(key, target=1)

        for idx in range(len(key_loc)):
            key_rel = get_relation(key_loc, idx)
            if lock_rel == key_rel:
                return True

            valid_rel = len([x for x in lock_rel if x in key_rel])
            if len(lock_rel) == valid_rel:
                for k in key_rel:
                    ny = lock_loc[0][0] - k[0]
                    nx = lock_loc[0][1] - k[1]
                    if ny < 0 or ny >= N or nx < 0 or nx >= N:
                        continue
                    if lock[ny][nx]:
                        break
                else:
                    return True

        key = [list(reversed(l)) for l in zip(*key)]
    else:
        return False

    
def get_location(lst, target=1):
    location = []
    for i in range(len(lst)):
        for j in range(len(lst)):
            if lst[i][j] == target:
                location.append((i, j))
    return location


def get_relation(lst, idx):
    relation = []
    if lst:
        l1 = lst[idx]
        lst_copy = lst[:]
        lst_copy.pop(idx)
        for l2 in lst_copy:
            relation.append((l1[0] - l2[0], l1[1] - l2[1]))
    return relation