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

문제 링크

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

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

풀이 

- 완전 탐색으로 풀이 

열쇠를 회전과 이동하여 끼웠을 때 자물쇠가 모두 1로 구성되면 열릴 수 있는 것이다. 

따라서 board의 중간에 자물쇠를 두고 왼쪽, 오른쪽, 위, 아래 열쇠의 크기만큼 확장시킨다. 

board의 위치에서 열쇠를 회전시킨 4가지 경우에 대하여 끼우고 자물쇠가 모두 1로 구성되었는지 확인한다. 

# 90도 회전 
def rotate(key, m):
    tmp = [ [0] * m for _ in range(m) ]
    
    for i in range(m):
        for j in range(m):
            tmp[j][m-1-i] = key[i][j]
            
    return tmp
   
# 열 수 있는지 확인 
def check(board, n, m):
    for i in range(n):
        for j in range(n):
        	# 1이 아니면 
            if board[m+i][m+j] != 1 :
                return False 
                
    # 모두 1로 구성되어 있으면 
    return True 
    
def solution(key, lock):
    answer = True
    m = len(key)
    n = len(lock)
    
    # 자물쇠 늘리기 
    board = [ [0] * (m*2 + n) for _ in range(m*2+n)]
    
    # 가운데 자물쇠 놓기 
    for i in range(n):
        for j in range(n):
            board[m+i][m+j] = lock[i][j]
    
    rotate_key = key
    for _ in range(4):
    	# 회전시킨 key 
        rotate_key = rotate(rotate_key,m)
        
        # board의 각 위치에 대하여 
        for i in range(1,m+n):
            for j in range(1,m+n):
                
                # 열쇠 끼우기 
                for a in range(m):
                    for b in range(m):
                        if rotate_key[a][b] == 1 :
                            board[i+a][j+b] += 1 
                
                # 열릴 수 있는지 확인 
                if check(board, n, m):
                    return True 
                
                # 열쇠 제거 
                for a in range(m):
                    for b in range(m):
                        if rotate_key[a][b] == 1 :
                            board[i+a][j+b] -= 1 
        
    return False

k = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
l = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
print(solution(k,l))

열쇠 인덱스 위치만 저장해서 풀어보았다. 

def run(N, M, index, lock, cnt):
    
    for x in range(-M + 1, N ):
        for y in range(-M + 1, N ):
            check = 0
            result = True
            
            for i, j in index:
                key_x = i + x
                key_y = j + y
                
                # lock 배열 크기 넘어감
                if key_x not in range(N) or key_y not in range(N):
                    continue
                # 열쇠의 돌기와 자물쇠의 돌기가 맞을 때 실패 
                if lock[key_x][key_y] :
                    result = False 
                    break
                # 홈이 맞을 때
                if lock[key_x][key_y] == 0:
                    check += 1
            
            # 열쇠의 돌기와 자물쇠의 돌기가 맞지 않고 
            if result :
            	# 홈이 다 맞았으면 
                if cnt == check:
                    return True

    return False

def solution(key, lock):
    answer = False
    N = len(lock)
    M = len(key)
    index = []

    # key index 저장
    for i in range(M):
        for j in range(M):
            if key[i][j] == 1:
                index.append([i,j])

    if len(index) == 0:
        return False

    # lock 홈 개수 저장
    cnt = 0
    for i in range(N):
        for j in range(N):
            if lock[i][j] == 0:
                cnt += 1

	# 회전 시키기 전 
    answer = run(N, M, index, lock, cnt)
    # 맞출 수 있으면 통과 
    if answer == True:
        return answer

    # 90도씩 회전
    for k in range(3):
        temp = []
        for x, y in index:
            if k == 0:
                n_x, n_y = y, (M-1) - x
            elif k == 1:
                n_x, n_y = (M-1) - x, (M-1) - y
            elif k == 2:
                n_x, n_y = (M-1) - y, x
            temp.append([n_x, n_y])

        answer = run(N, M, temp, lock, cnt)
        if answer :
            return answer 

    return answer