[알고리즘/파이썬] 프로그래머스 - 자물쇠와 열쇠

문제

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

프로그래머스

 

풀이

논리는 떠올렸는데... 중간에 실수한 것들 디버깅하면서 찾아내는게 참 힘들었다. 늘 느끼지만 이런 시뮬레이션은.. 처음부터 정신 똑바로 차리고 푸는게 좋은듯하다. 실수 찾아내기 넘 힘들어...

 

1. 처음에 자물쇠가 다 1로 채워져있으면 열쇠가 굳이 필요없으므로 True를 리턴한다.

2. 키를 90도 회전한다.

3. 회전한 키가 lock에 들어갈 수 있는 모든 경우의 수를 다 탐색한다. (여기서 범위를 잘 설정해야 한다)

4. 3에서 만든 키를 갖고 키나 락 둘 중에 하나만 1인 경우(돌기는 돌기와 만날 수 없고, 둘 다 0 이면 홈이 파져있는거기 때문에)가 lock의 모든 칸에 적용된다면 키가 자물쇠를 열었다고 판단하고 True를 반환한다.

 

 

 

코드

def solution(key, lock):
    answer = False
    lock_n = len(lock)
    key_n = len(key)
    
    flag = 0
    for a in lock:
        for b in a:
            if b == 0:
                flag = 1
                break
                
    if flag == 0:
        return True
            
    def check_key_and_lock(key):
        nonlocal key_n
        nonlocal lock_n
        nonlocal lock
        
        for i in range(lock_n):
            for j in range(lock_n):
                if key[i][j] == lock[i][j]:
                    return False
                
        return True
                        
    def move_key(key):
        nonlocal key_n
        nonlocal lock_n
        nonlocal answer
        
        start = -1*key_n+1
        end = lock_n + key_n
        for i in range(start,end):
            for j in range(start,end):
                new_key = [[0 for _ in range(lock_n)] for _ in range(lock_n)]
                for a in range(key_n):
                    for b in range(key_n):
                        new_a = a + i
                        new_b = b + j
                        
                        # 범위 벗어나면
                        if new_a < 0 or new_b<0 or new_a>=lock_n or new_b>=lock_n:
                            continue
                        else:
                            new_key[new_a][new_b] = key[a][b]
                            
                result = check_key_and_lock(new_key)
                if result:
                    answer = True
                    return
                              
    for _ in range(4):
        # 90도 회전
        new_key = list(map(list, zip(*key[::-1])))
        key = new_key[:]
        move_key(new_key)
        
    return answer