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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60059

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

 

브루트포스로 해결했다.

열쇠의 칸중 최소 한개가 자물쇠에 올수 있도록 범위를 확장해서 열쇠를 올려보면 된다.

 

문제의 테케 1번으로 설명하면 아래와 같다.

key는 3x3이고 lock는 3x3이다.

lock에 key의 최소 한칸이 오려면 key의 크기의 -1만큼 왼쪽위로 범위를 확장하고 올려보면 된다.

발로 그림...

위 그림처럼 3x3 lock를 -2,-2에서 2,2까지 있는 5x5범위로 확장하여 열쇠를 올려본다면 최소 하나의 열쇠칸이 자물쇠에 올라가게 된다. 이후 해당 범위에서 열쇠를 돌리면서 확인하면 된다.

이때 인덱스가 열쇠의 범위를 벗어난 칸은 그냥 지나치면 된다. 범위 밖을 나간 열쇠는 무시해도된다고 문제에 주어진다.

 

def solution(k, l):
    global m, n, key, lock, empty_cnt
    key = k
    lock = l
    m = len(key)
    n = len(lock)
    empty_cnt = 0

    for row in lock:
        empty_cnt += row.count(0)

    for _ in range(4):
        if move_key():
            return True
        key = rotate_key(key)

    return False


def move_key():
    sx = sy = 1 - m
    ex = ey = n
    for x in range(sx, ex):
        for y in range(sy, ey):
            if check_key(x, y):
                return True
    return False


def check_key(sx, sy):
    cnt = 0
    kx = -1
    for x in range(sx, sx + m):
        kx += 1
        if x < 0:
            continue
        elif x >= n:
            break
        ky = -1
        for y in range(sy, sy + m):
            ky += 1
            if y < 0:
                continue
            elif y >= n:
                break
            if lock[x][y] == 0 and key[kx][ky] == 1:
                cnt += 1
            elif lock[x][y]==key[kx][ky]:
                return False
    if cnt == empty_cnt:
        return True
    return False


def rotate_key(key):
    tmp = [[0] * m for _ in range(m)]

    for x in range(m):
        for y in range(m):
            tmp[y][m - x - 1] = key[x][y]

    return tmp