[프로그래머스 Level3] 자물쇠와 열쇠 - 파이썬(Python) - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

 

---

 먼저, key의 한 변의 길이인 m과 lock의 한 변의 길이인 n을 구한다.

key가 lock과 닿은 상태로 모든 부분을 탐색해볼 수 있도록 각 행과 열의 길이가 2*m+(n-2)인 1로 채워진 board 행렬을 만든 후, board 행렬의 정 가운데에 lock 행렬을 대입한다.

board가 모두 만들어진 이후 열쇠를 하나씩 넣어봤을 때 자물쇠와 닿을 수 있는 행렬의 가장 왼쪽, 윗쪽 인덱스는 0~m+n-2이다. 해당 인덱스를 이용해서 한 경우씩 열쇠가 자물쇠를 열 수 있는지 확인해보아야 한다.

# 열쇠가 모든 자물쇠를 탐색할 수 있는 board 행렬 만들기
m, n = len(key), len(lock)
board = [[1 for _ in range(2*m+(n-2))] for _ in range(2*m+(n-2))]
    
# board의 중앙에 자물쇠의 정보 입력하기
for i in range(m-1, m+n-1):
    for j in range(m-1, m+n-1):
        board[i][j] = lock[i-(m-1)][j-(m-1)]

# 자물쇠와 닿을 수 있는 모든 부분 탐색
for i in range(m+n-1):
    for j in range(m+n-1):
        if unlocked(board, key, i, j, m, n, emptyCnt):
            return True
return False

 

내가 이 부분에서 계속해서 23, 25, 33 테스트 케이스만 틀렸었는데, 자물쇠의 공간 내에 열쇠 행렬이 닿을 때, 자물쇠의 막힌 곳과 열쇠의 막힌 곳이 만나는 경우를 제외하면 해결된다ㅠ

열쇠가 회전할 수 있으므로 rotage_90() 함수를 이용해서 행렬을 4번 회전하며 자물쇠를 열 수 있는지 확인한다.

def rotate_90(arr, n): # 행렬 90도 회전하기
    res = [[0] * n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            res[c][n-1-r] = arr[r][c]
    return res

def unlocked(board, key, y, x, m, n, emptyCnt): # 열쇠로 자물쇠를 열 수 있는지 확인
    for _ in range(4):
        cnt = 0 # 자물쇠의 영역 안 빈 곳에 열쇠가 들어가면 개수를 센다.
        for i in range(y, y+m):
            for j in range(x, x+m):
                if (i<m-1 or m+n-2<i) or (j<m-1 or m+n-2<j):
                    continue
                if key[i-y][j-x] == 1:
                    if board[i][j] == 1:
                        cnt = -1
                    if board[i][j] == 0:
                        cnt += 1
        if cnt == emptyCnt:
            return True
        key = rotate_90(key, len(key)) # 행렬 90도 회전하기
    return False

 

 

 

<< 전체 코드 >>

def rotate_90(arr, n): # 행렬 90도 회전하기
    res = [[0] * n for _ in range(n)]
    for r in range(n):
        for c in range(n):
            res[c][n-1-r] = arr[r][c]
    return res
            
def unlocked(board, key, y, x, m, n, emptyCnt): # 열쇠로 자물쇠를 열 수 있는지 확인
    for _ in range(4):
        cnt = 0 # 자물쇠의 영역 안 빈 곳에 열쇠가 들어가면 개수를 센다.
        for i in range(y, y+m):
            for j in range(x, x+m):
                if (i<m-1 or m+n-2<i) or (j<m-1 or m+n-2<j):
                    continue
                if key[i-y][j-x] == 1:
                    if board[i][j] == 1:
                        cnt = -1
                    if board[i][j] == 0:
                        cnt += 1
        if cnt == emptyCnt:
            return True
        key = rotate_90(key, len(key)) # 행렬 90도 회전하기
    return False

def solution(key, lock):
    emptyCnt = 0
    for row in lock:
        emptyCnt += row.count(0)
    # 열쇠가 모든 자물쇠를 탐색할 수 있는 board 행렬 만들기
    m, n = len(key), len(lock)
    board = [[1 for _ in range(2*m+(n-2))] for _ in range(2*m+(n-2))]
    
    # board의 중앙에 자물쇠의 정보 입력하기
    for i in range(m-1, m+n-1):
        for j in range(m-1, m+n-1):
            board[i][j] = lock[i-(m-1)][j-(m-1)]

    # 자물쇠와 닿을 수 있는 모든 부분 탐색
    for i in range(m+n-1):
        for j in range(m+n-1):
            if unlocked(board, key, i, j, m, n, emptyCnt):
                return True
    return False