title: "[프로그래머스] 자물쇠와 열쇠 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/60059"
description: "프로그래머스 Level 3 문제 [자물쇠와 열쇠]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import copy

def solution(key, lock):
    # 자물쇠의 크기 N, 열쇠의 크기 M
    # 자물쇠를 양 옆으로 M-1만큼 확장하고, 확장된 칸은 모두 1로 채웁니다.
    # 이러면 홈 부분의 좌표는 (r + (M-1), c + (M-1))입니다.
    # 열쇠를 4가지로 회전한 버전을 sliding window 방식으로
    # 자물쇠에 대보고, 자물쇠 범위 내에서 XOR한 값들이 모두 1이 아니면
    # false를 리턴합니다.
    N, M = len(lock), len(key)
    
    # 우선 홈 부분의 좌표들을 저장해둡니다.
    rooms = []
    for r, row in enumerate(lock):
        for c, num in enumerate(row):
            if num == 0:
                rooms.append( (r + (M-1), c + (M-1)) )
                
    # 자물쇠를 확장합니다.
    newlock = [ [1] * (2*M - 2 + N) for _ in range(M-1) ]
    for r, row in enumerate(lock):
        newlock += [[1] * (M-1) + row + [1] * (M-1)]
    newlock += [ [1] * (2*M - 2 + N) for _ in range(M-1) ]
    
    # 4가지 버전의, 회전한 열쇠들을 마련합니다.
    # 그대로
    turn0 = key
    # 시계방향 90도
    turn90 = copy.deepcopy(key)
    for r, row in enumerate(key):
        for c, num in enumerate(row):
            turn90[c][M-1-r] = num
    # 180도
    turn180 = copy.deepcopy(key)
    for r, row in enumerate(key):
        for c, num in enumerate(row):
            turn180[M-1-r][M-1-c] = num
    # 반시계방향 90도
    turn270 = copy.deepcopy(key)
    for r, row in enumerate(key):
        for c, num in enumerate(row):
            turn270[M-1-c][r] = num
            
    # 키들을 대봅니다.
    keys = [turn0, turn90, turn180, turn270]
    for k in keys:
        for r in range(N + M + 1):
            for c in range(N + M + 1):
                # 열쇠의 왼쪽 위 부분이 (r, c)입니다.
                # 즉 열쇠가 커버하는 부분은 (r, c) ~ (r + (M-1), c + (M-1))
                # 까지입니다.
                l = copy.deepcopy(newlock)
                
                # 열쇠가 홈을 커버하지 못하면 검사해볼 필요가 없습니다.
                skip = False
                for roomr, roomc in rooms:
                    if not (r <= roomr < r+M and c <= roomc < c+M):
                        skip = True
                        break
                if skip:
                    continue
                
                found = True
                for r1 in range( max(r, M-1), min(M+N-1, r+M) ):
                    for c1 in range( max(c, M-1), min(M+N-1, c+M) ):
                        if k[r1-r][c1-c] ^ l[r1][c1] == 0:
                            found = False
                            break
                    if not found:
                        break
                if found:
                    return True
    
    return False

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges