import Foundation
func solution(_ key:[[Int]], _ lock:[[Int]]) -> Bool {
var rotatedKey = key
for _ in 0..<4 { // 4번 회전시킨다
if canSolveLock(rotatedKey, lock) { // 이리저리 끼워맞춰 푸는게 가능한지
return true
}
rotatedKey = rotate(rotatedKey)
}
return false
}
// 시계방향 키 회전
func rotate(_ key: [[Int]]) -> [[Int]] {
let M = key.count - 1
var rotateKey: [[Int]] = (0...M).map { _ -> [Int] in // 일단 빈값 넣기
(0...M).map { _ in 0 }
}
for i in 0...M {
for j in 0...M where key[i][j] == 1 {
rotateKey[j][M - i] = 1
}
}
return rotateKey
}
// 모서리부터 쭉 이동시켜서 끼워맞춰본다
func canSolveLock(_ key: [[Int]], _ lock: [[Int]]) -> Bool {
let M = lock.count + ((key.count - 1) * 2)
for i in 0...M {
for j in 0...M {
let lockWithKey = combine(i, j, key, lock)
if isPerfect(lockWithKey) {
return true
}
}
}
return false
}
// 끼워맞추기
func combine(_ i: Int, _ j: Int, _ key: [[Int]], _ lock: [[Int]]) -> [[Int]] {
let N = key.count - 1
let M = lock.count - 1
var lockWithKey = lock
for keyI in i...i+N {
let x = keyI - N
if x < 0 || x > M {
continue
}
for keyJ in j...j+N {
let y = keyJ - N
if y < 0 || y > M {
continue
}
if lock[x][y] == key[keyI - i][keyJ - j] { // 끼워맞출곳이 서로 같다면 탈출
lockWithKey[0][0] = 0 // isPerfect()에서 빨리 탈출하기 위함
return lockWithKey
} else if lock[x][y] == 0 {
lockWithKey[x][y] = 1
}
}
}
return lockWithKey
}
// 락이 풀렸는지 확인
func isPerfect(_ lock: [[Int]]) -> Bool {
for colum in lock {
for row in colum {
if row != 1 {
return false
}
}
}
return true
}
문제를 어떻게 풀지 구상은 금방 마쳤지만 머리속으로 키와 락이 2차원배열로 어떻게 끼워맞춰질지 코드로 짜느라 힘들었던 문제.
반복문을 엄청타서 복잡도에서 문제가 생길까 조마조마했지만 다행히 복잡도까지 요구하는 문제는 아니었다.