문제 링크 (opens new window)

풀이

1. 처음에는 브루트포스로 풀어볼려고 했음. 재귀적으로 함수를 호출하며 6^6 정도의 시간을 생각했었지만 SCV 체력이 60으로 시작하는 경우 60부터 1까지 곱한 값에 6^6을 곱해야 한다는 것을 알게됨 -> 시간초과
2. BFS풀이를 3차원으로 확장하여 풀이
3. 초기에 주어지는 SCV 체력을 갯수에 상관없이 3개로 맞춘다. 1개 혹은 2개 입력시 남은 공간은 죽은 SCV로 가정한다.
4. 초기 SCV 체력을 3차원 박스에서의 첫 위치 좌표로 생각한다.
5. 모든 SCV가 죽었을때의 좌표를 [0,0,0]으로 생각하여 뮤탈리스크 공격을 간선으로 ny, nx, nz를 생각한다.

import Foundation

let n = Int(readLine()!)!
var scvInput = readLine()!.split(separator: " ").map { Int($0)! }

if n < 3 {
    scvInput += .init(repeating: 0, count: 3 - n)
}

var visited: [[[Int]]] = .init(repeating: .init(repeating: .init(repeating: 0, count: 64), count: 64), count: 64)
var attackList: [[Int]] = [
    [1,3,9],
    [1,9,3],
    [3,1,9],
    [3,9,1],
    [9,1,3],
    [9,3,1]
]

struct Queue<T> {
    var array: [T?] = []
    var head = 0

    var isEmpty: Bool {
        return count == 0
    }

    var count: Int {
        return array.count - head
    }

    mutating func enqueue(_ element: T) {
        array.append(element)
    }

    mutating func dequeue() -> T? {
        guard head < array.count,
              let element = array[head] else { return nil}

        array[head] = nil
        head += 1

        let percentage = Double(head) / Double(array.count)
        if percentage > 0.25 && array.count > 50 {
            array.removeFirst(head)
            head = 0
        }

        return element
    }

    var front: T? {
        if isEmpty {
            return nil
        } else {
            return array[head]
        }
    }
}

var q = Queue<(Int, Int, Int)>()
q.enqueue((scvInput[0], scvInput[1], scvInput[2]))
visited[scvInput[0]][scvInput[1]][scvInput[2]] = 1

while(true) {
    guard let there = q.front else { break }
    _ = q.dequeue()

    for i in attackList {
        let ny = max(there.0 - i[0], 0)
        let nx = max(there.1 - i[1], 0)
        let nz = max(there.2 - i[2], 0)

        if ny < 0 || nx < 0 || nz < 0 || ny >= 60 || nx >= 60 || nz >= 60 || visited[ny][nx][nz] != 0 {
            continue
        }

        visited[ny][nx][nz] = visited[there.0][there.1][there.2] + 1
        q.enqueue((ny, nx, nz))
    }
}

print(visited[0][0][0] - 1)