[백준] 자물쇠와 열쇠

자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059?language=python3#

프로그래머스

 

• • 열쇠 회전
    • 열쇠(key)를 시계 방향으로 90도씩 회전하여 총 4가지 모양 생성
  • 확장된 자물쇠 보드 생성
    • 열쇠가 자물쇠 전체를 덮으며 이동할 수 있도록, 자물쇠(lock)를 중심에 배치한 확장된 보드(graph) 생성
    • 보드의 크기는 n + 2 * (m - 1)로 설정하여 열쇠가 모든 위치에서 시도 가능하도록 구성
  • 열쇠와 자물쇠 맞추기 검사
    • 각 회전된 열쇠를 확장된 보드 내 모든 가능한 위치에 놓아보며 자물쇠와 맞는지 확인
    • 열쇠의 돌기(1)와 자물쇠의 홈(0)이 정확히 일치해야 하며, 돌기끼리 겹치면 실패
  • 자물쇠 해제 여부 판단
    • 열쇠를 놓은 뒤 자물쇠 원래 영역 내 모든 값이 1이면 자물쇠가 열림
    • 한 번이라도 맞는 경우가 있다면 True, 끝까지 없으면 False 반환내 풀이

import copy

def solution(key, lock):
    n=len(lock)
    m=len(key)
    answer = True
    
    key_lst=[]
    key_lst.append(key)
    for _ in range(3):
        row=[]
        for j in range(m):
            tmp=[]
            for i in range(m-1,-1,-1):
                tmp.append(key_lst[-1][i][j])
            row.append(tmp)
        key_lst.append(row)
    
    graph=[]
    for i in range(2*m+n-2):
        if i<m-1 or i>(m+n-2):
            graph.append([-1 for _ in range(2*m+n-2)])
            continue
        idx=i-(m-1)
        tmp=[-1 for _ in range(m-1)]
        tmp+=lock[idx]
        tmp+=[-1 for _ in range(m-1)]
        graph.append(tmp)
    
    def check(k,start_i,start_j):
        nonlocal n,m
        nonlocal graph
        
        lock2=copy.deepcopy(graph)
        for i in range(m):
            for j in range(m):
                if graph[start_i+i][start_j+j]==-1:
                    continue
                    
                if k[i][j]==1 and graph[start_i+i][start_j+j]==1:
                    return False
                elif k[i][j]==1 and graph[start_i+i][start_j+j]==0:
                    lock2[start_i+i][start_j+j]=1
        
        if istrue(lock2):
            return True
        else:
            return False
        
    def istrue(lock_tmp):
        nonlocal n
        
        for i in range(m,n+m):
            for j in range(m,n+m):
                if lock_tmp[i][j]==0:
                    return False
        
        return True
                 
    for k in key_lst:
        for i in range(m+n-1):
            for j in range(m+n-1):
                if check(k,i,j):
                    return True
                
                
    return False