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

자물쇠와 열쇠

문제

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

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

코드

이 문제는 2차원배열의 범위가 작기때문에 모든 경우를 탐색하면 풀수있다.

하지만 모든 경우를 탐색하는것도 생각보다 어려웠다.

길이가 N인 2차원 배열 lock을 (M -1) * 2 + N 의 배열로 늘려서 lock을 가운데에 넣고 key를 0, 0부터 90도씩 회전시켜나가면서 모든 위치를 확인하면서 풀었다.

1. empty_lock 함수를 통해 자물쇠에서 비어있는 위치와 잠겨있는 위치를 찾아낸뒤 empty, filled로 반환했다.
2. rotate_90함수를 통해 key의 위치를 90도씩 돌리고 90도 돌리고난뒤의 key의 위치를 one_list 리스트에 푸쉬했다.
3. find함수에서 key의 위치가 담긴 one_list에 2중 for문 통해 확장된 2차원 배열의 모든 위치를 탐색했다.
4. 탐색을 하면서 key의 위치가 empty의 모든 값을 포함하면서 filled의 모든값과는 겹치지 않을때 True로 반환했다.

import copy
def empty_lock(lock,n,m):
    empty = []  # 자물쇠가 빈부분
    filled = [] # 자물쇠가 있는부분
    for i in range(n):
        for j in range(n):
            if not lock[i][j]:
                empty.append([i+m-1,j+m-1])
            else:
                filled.append([i+m-1,j+m-1])
    return tuple(empty), tuple(filled)

def find(one_list,e,empty,filled):
    for i in range(e):
        for j in range(e):
            key_move = []  # 열쇠의 위치를 이동
            for x,y in one_list:
                if 0<=x+i<e and 0<= y+j<e:
                    key_move.append([x+i,y+j])
                else:
                    break
            if len(key_move) == len(one_list):
                key_move = tuple(key_move)
                flag = True

                for zero in empty:
                    if zero in key_move:
                        continue
                    else:
                        flag = False
                        break
                if flag:
                    for one in filled:
                        if one in key_move:
                            flag = False
                            break
                    if flag:
                        return True
    return False

def rotate_90(key,empty,m,e,filled):
    ret = copy.deepcopy(key)
    for _ in range(4):
        one_list = []
        # 한바퀴 씩 돌리면서 확인해봄
        tmp = [[0] * m for _ in range(m)]
        for x in range(m):
            for y in range(m):
                tmp[y][m - 1 - x] = ret[x][y]
                if tmp[y][m - 1 - x] == 1:
                    one_list.append([y,m - 1 - x])
        ret = tmp.copy()
        if find(one_list,e,empty,filled):
            return True
    return False

def solution(key, lock):
    n = len(lock)
    m = len(key)
    empty,filled = empty_lock(lock,n,m)
    e = (m - 1) * 2 + n
    answer = rotate_90(key,empty,m,e,filled)
    return answer