문제 링크 (opens new window)

문제

1. 완탐
2. 시간복잡도 - 64C3 x (64 + 64) = 약 500만, 완탐으로 풀어도 됨

import Foundation

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]
        }
    }
}

let NM = readLine()!.split(separator: " ").map { Int($0)! }; let N = NM[0]; let M = NM[1]
var adj: [[Int]] = .init(repeating: .init(repeating: 0, count: M), count: N)
var visited: [[Bool]] = .init(repeating: .init(repeating: false, count: M), count: N)
let dy = [-1, 0, 1, 0]; let dx = [0, 1, 0, -1]
var virus: [(Int, Int)] = []
var walls: [(Int, Int)] = []
var result = 0

for row in 0..<N {
    adj[row] = readLine()!.split(separator: " ").enumerated().map { col, element in
        let value = Int(element)!
        if value == 2 {
            virus.append((row, col))
        }
        if value == 0 {
            walls.append((row, col))
        }
        return value
    }
}

func combination<T>(_ elements: [T], _ k: Int) -> [[T]] {
    var ret: [[T]] = []

    func combi(_ index: Int, _ now: [T]) {
        if now.count == k {
            ret.append(now)
            return
        }

        for i in index..<elements.count {
            combi(i + 1, now + [elements[i]])
        }
    }
    combi(0, [])
    return ret
}

func check() -> Int {
    var ret = 0
    for i in 0..<N {
        for j in 0..<M {
            if adj[i][j] == 0 { ret += 1}
        }
    }
    return ret
}

// MARK: BFS
var adjCopy = adj
for wall in combination(walls, 3) {
    adj = adjCopy
    visited = .init(repeating: .init(repeating: false, count: M), count: N)
    adj[wall[0].0][wall[0].1] = 1
    adj[wall[1].0][wall[1].1] = 1
    adj[wall[2].0][wall[2].1] = 1

    var q = Queue<(Int, Int)>()
    for pos in virus {
        q.enqueue(pos)
        visited[pos.0][pos.1] = true
    }

    while !q.isEmpty {
        guard let there = q.dequeue() else { break }

        for i in 0..<4 {
            let ny = dy[i] + there.0
            let nx = dx[i] + there.1

            if ny < 0 || nx < 0 || ny >= N || nx >= M || visited[ny][nx] || adj[ny][nx] == 2 || adj[ny][nx] == 1 { continue }

            visited[ny][nx] = true
            adj[ny][nx] = 2
            q.enqueue((ny, nx))
        }
    }
    result = max(result, check())
}

print(result)