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

🕵🏻  문제 해석 

---

고고학자인  "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 잠겨있는 자물쇠는 격자 한 칸의 크기가  1 x 1인  N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

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

• key는 M x M(3 ≤ M ≤ 20, M은 자연수) 크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
• 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

🤔 풀이 과정

---

먼저, 문제를 보고 정사각 행렬 형태로 주어진 열쇠를 시계 방향으로 90도 회전시키는 함수가 제일 먼저 필요하겠구나 싶었습니다.  

func rotateKey90DegreesClockwise(_ key: [[Int]]) -> [[Int]] {
     var rotatedKey = [[Int]](repeating: [Int](repeating: 0, count: M), count: M)
     
     for col in 0..<M {
         for row in (0..<M).reversed() {
              rotatedKey[col][M - 1 - row] = key[row][col]
         }
     }
        
     return rotatedKey
}

저는 다음과 같이 작성했는데, 행에 있던 데이터들이 회전된 행렬에서는 열 데이터가 되므로 3 X 3 정도의 예시 행렬을 보면서 그에 맞추어 반복문을  작성해보았습니다. 구글에 행렬 회전에 대한 설명이 자세하게 나와있으므로 이 부분은 건너뛰어도 되겠죠? 🥺

자 이제, 열쇠를 회전 시킬 수 있으니 자물쇠에 맞추어 보아야겠습니다. 회전시킨 열쇠 행렬을 가능한 모든 위치마다 자물쇠 행렬과 더 해주었을 때 자물쇠 행렬의 값들이 모두 1이 되면 자물쇠가 열린다고 판단할 수 있습니다. 

만약 자물쇠 행렬의 값중에 0이 존재한다면, 채워지지 않은 홈이 있다는 것이고 2가 존재한다면 자물쇠의 돌기와 열쇠의 돌기가 만났다고 판단하고 이 경우에는 false 처리를 해주었습니다. 

설명을 돕기 위해 문제에서 예시로 준 3 X 3 자물쇠와 열쇠를 바탕으로 행렬 표를 작성해봤습니다.😅 이 표는 확장된 자물쇠 영역을 표현한 것인데요, 문제에서 열쇠의 크기인 N은 항상 M이하라고 했기 때문에 어느 방향으로 열쇠를 겹치던 3 * N X 3 * N 행렬 안에서 겹쳐지게 된다고 판단해서 이렇게 해주었습니다. 노란색의 셀은 행렬의 인덱스입니다!

원래 자물쇠 행렬은 확장된 행렬 안에서 [N..<2 * N][N..<2 * N]에 위치하고 자물쇠 행렬영역과 열쇠 행렬 영역이 하나 이상은 겹쳐야 하기 때문에 (겹치지 않으면 자물쇠에 열쇠를 안 끼우는 격이 됩니다..) 열쇠 행렬이 위치할 수 있는 영역은 빨간색으로 테두리 쳐둔 부분이 됩니다.

보통 이중 for문으로 행렬을 탐색할 때 좌상단부터 탐색을 하기 때문에 빨간색 영역을 열쇠 행렬인 M X M과 매칭 시켜 탐색하려면 그 탐색을 시작하는 좌표가 [N - M + 1 ..< 2 * N] [N - M + 1 ..< 2 * N] 에 위치하게 됩니다. 

이를 표로 표현하면 다음과 같습니다.

이렇게 탐색 지점을 파악하고 나서 입력받은 열쇠 행렬을 회전시키며 해당 영역을 탐색해보고 자물쇠가 열리는 케이스를 판단해주면 될 것 같습니다.  표로 만들긴 했는데.. 이해에 도움이 되었으면 합니다.😂 혹시나 문제 설명에 오류가 있으면 댓글로 알려주세요!

📦  문제 풀이 & 코드

---

import Foundation

func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
    let M = key.count
    let N = lock.count
    
    // 3 * N X 3 * N 으로 확장시킨 자물쇠 행렬
    var extendedLock = [[Int]](repeating: [Int](repeating: 0, count: 3 * N), count: 3 * N)
    
    // 확장된 행렬에서 원래의 자물쇠행렬이 위치하는 범위
    let extendedRange = N..<2 * N

    // 90도 시계방향 회전
    func rotateKey90DegreesClockwise(_ key: [[Int]]) -> [[Int]] {
        var rotatedKey = [[Int]](repeating: [Int](repeating: 0, count: M), count: M)
        for col in 0..<M {
            for row in (0..<M).reversed() {
                rotatedKey[col][M - 1 - row] = key[row][col]
            }
        }
        return rotatedKey
    }
    
    // 확장된 행렬에서 자물쇠위치를 탐색하며 열리는지 판단
    func canOpen(_ lock: [[Int]]) -> Bool {
        for i in extendedRange {
            for j in extendedRange {
                // 0 이 존재하면 채워지지 않은 홈, 2이면 돌기끼리 만난 경우 false 리턴
                if lock[i][j] != 1 {
                    return false
                }
            }
        }
        return true
    }
    
    // 입력받았을 때, 자물쇠가 모두 1인 경우 열려있으므로 true 리턴
    if (lock.filter{$0.contains(0)}).isEmpty {
        return true
    }
    
    // 확장
    for i in 0..<N {
        for j in 0..<N {
            extendedLock[i + N][j + N] = lock[i][j]
        }
    }
    
    var tempKey = key
    var tempExtendedLock = extendedLock
    
    for _ in 0..<4 {
        for i in (N - M + 1)..<2 * N {
            for j in (N - M + 1)..<2 * N  {
                tempExtendedLock = extendedLock
                for row in 0..<M {
                    for col in 0..<M {
                        tempExtendedLock[i + row][j + col] += tempKey[row][col]
                    }
                }
                
                if canOpen(tempExtendedLock) {
                    return true
                }
            }
        }
        // 키를 회전시키면서 열리는지 체크
        tempKey = rotateKey90DegreesClockwise(tempKey)
    }
    return false
}

🤷🏻‍♂️ 더 생각해보기

---

제 경우는 canOpen이라는 함수를 따로 작성하여 이중 for 문을 통해 일일이 자물쇠영역을 확인해주었지만, 호출 전에 값을 더하는 과정에서 1이 아닌 값이 나오면 바로 반복문을 break하는 처리를 하면 좀 더 효율적인 풀이가 될 듯 싶습니다. 저도 좀 더 빠르게 풀 수있는 방법을 공부해야겠네요.🥲

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

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