프로그래머스 자물쇠와 열쇠 코드 및 해설 (파이썬)

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

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

 

💡 각 좌표의 차이를 통해 대응관계를 알아내어 풀이합니다 

 

다음의 2가지 조건을 충족하면 True를 반환하도록 풀이했습니다. 만족하지 않으면 key를 90도씩 회전시켜보면서 다시 조건을 따져보게 했고, 끝까지 안되면 False를 반환하도록 했습니다.

 

1. 열쇠 모양이 맞을 것

 

lock이 0인 부분의 모양과 key가 1인 부분의 모양이 같아야 합니다.

주어진 lock에서 0인 부분의 좌표(lock0)와 그 좌표들의 차를 통해 관계(lock_relations)를 표현했고, key를 각각 회전했을 때 1인 부분의 좌표(key1)들 중 앞서 구한 lock에서 0인 부분의 관계(lock_relations)와 같은 관계를 갖는 것들이 있는 걸 찾는 방식으로 풀이했습니다.

 

예를 들어 lock에서 0인 좌표가 (1,2), (2,1)로 2개 있고, 이들의 차이 (2-1, 1-2) = (1,-1) 을 통해 같은 모양으로 배치된 좌표들을 찾을 수 있습니다. (0,1)과 (1,0)도 차이가 (1,-1)이므로 똑같이 대각선 아래에 있는 관계로 모양이 같은 것을 확인할 수 있습니다.

 

2. 홈끼리 부딪히지 않을 것
lock과 key가 서로 대응되는 좌표 외에 나머지 key가(residual) 1인 부분의 좌표는 lock 영역 내에 존재하면 안 됩니다.

현재 열쇠를 맞추고 있는 상황에서 key의 좌표가 lock의 어느 좌표에 대응되는지 계산하고, 이때 모든 residual이 lock 영역 밖에 있어 홈끼리 부딪히지 않으면 True를 반환하도록 했습니다.

 

from collections import deque 

# 주어진 n*n 행렬을 회전하는 class 
class rotation:
    def __init__(self, x):
        self.x = x
        self.n = len(x)
    
    # self.x를 오른쪽으로 90도 회전 
    def right90(self):
        result = []
        for i in range(self.n):
            temp = []
            for j in range(self.n):
                temp.append(self.x[j][i])
            result.append(temp[::-1])
        self.x = result

    # num만큼 오른쪽으로 90도 회전 
    def rotate(self, num):
        for i in range(num):
            self.right90()
        return self.x


# n*n 행렬 중 값이 val인 부분의 index들을 리스트로 반환 
def check_idx(matrix, val):
    result = []
    n = len(matrix)
    for i in range(n):
        for j in range(n):
            if matrix[i][j] == val:
                result.append((i,j))
    return result 

# 좌표들의 리스트들을 입력 받으면, 연속하는 각 좌표들의 차를 반환
# ex. [(0,2), (1,1), (2,1)]을 입력으로 받으면, [(1,-1), (1,0)]을 반환 
def check_relation(q):
    relations = []
    while q:
        cur = q.popleft()
        if q:
            x,y = cur
            a,b = q[0]
            relations.append((a-x, b-y))
    return relations

def solution(key, lock):
    n = len(lock)
    r = rotation(key)
                        
    # lock에서 0인 부분의 index 
    lock0 = deque(check_idx(lock, 0))
    
    # 열쇠를 꽂을 곳이 없음 
    if lock0 == deque():
        return True 
    
    # 0인 부분들 사이의 차(관계) 
    # ex. lock의 (1,2)와 (2,1)이 0이라면 lock_relations=[(1,-1)]
    lock_relations = check_relation(lock0.copy())

    # key는 4가지 회전 가능 
    for i in range(4):

        # 회전 후 key에서 1인 부분의 index
        key1 = check_idx(r.rotate(i), 1)
        
        possible_keys = []
    
        # 열쇠 모양 확인 
        for k in key1:
            # lock과 모양이 맞는 key의 위치들 
            shape_matching_keys = [k]
            cur_key = k
            for l in lock_relations:
                cur_key = tuple([sum(x) for x in zip(cur_key, l)])
                if cur_key in key1:
                    shape_matching_keys.append(cur_key)
            # 자물쇠의 모든 홈을 빈틈없이 채운 경우 
            if len(shape_matching_keys) == len(lock0):
                possible_keys.append(shape_matching_keys)
                
        
        # 열쇠 모양은 통과
        # 돌기끼리 안 부딪히는지 확인 
        for possible_key in possible_keys:
            
            # key가 1인 부분 중 자물쇠 홈에 대응하지 않는 나머지들 
            residual = [k for k in key1 if k not in possible_key]
            

            # 대응관계: key의 위치가 lock의 위치 어디에 해당하는지 
            # ex. key의 (0,1)이 lock의 (1,0)에 대응한다면 key2lock은 (1-0, 0-1) = (1,-1)
            # 그러면 key의 (2,0)은 lock의 (2,0) + (1,-1) = (3,-1)에 위치할 것을 알 수 있음 
            x,y = possible_key[0]
            a,b = lock0[0]
            key2lock = (a-x,b-y)
        
            count = 0
            for res in residual:
                pos = [sum(x) for x in zip(res, key2lock)]
                # 각 residual이 lock에서의 위치가 자물쇠 영역 바깥인 경우
                if (pos[0] not in range(n)) or (pos[1] not in range(n)):
                    count += 1 

            # 부딪힐 부분이 자물쇠 영역 밖에 있어서 상관 없는 경우 True 
            if count == len(residual):
                return True
                        
    return False