Swift) 백준 17142번 연구소3 - G3

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

틀이 되는 풀이는 금방 알았지만.. 예외처리 할것들이 많았던 문제. 

조합 + BFS + 부르트 포스를 이용하여 풀었다.

 

예외처리 할 부분은 비활성화된 바이러스의 처리 부분. 비활성화된 바이러스도 바이러스이므로 해당 부분을 다른 바이러스가 전이하지 않아도 바이러스가 존재한것으로 규정한다. 이에 따른 예외처리할것들이 꽤 있어서 고생했다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0]
let m = input[1]
var map: [[Int]] = []
var variousLocation: [(Int, Int)] = []
var comb: [(Int, Int)] = Array(repeating:(0,0) ,count:m)
let di = [-1,0,1,0]
let dj = [0,1,0,-1]

struct VarousLocation {
    let i: Int
    let j: Int
    let count: Int
    let variousCount: Int
    let isVariousBlock: Bool
}

for i in 0..<n {
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    for j in line.enumerated() {
        if j.element == 2 {
            variousLocation.append((i,j.offset))
        }
    }
    map.append(line)
}

func combination<T>(_ array: [T], _ n: Int) -> [[T]] {
    var result = [[T]]()
    if array.count < n { return result }
    func cycle(_ index: Int, _ now: [T]) {
        if now.count == n {
            result.append(now)
            return
        }
        for i in index..<array.count {
            cycle(i + 1, now + [array[i]])
        }
    }
    cycle(0,[])
    return result
}

func solution() -> Int {
    var answer = Int.max
    let combVarious = combination(variousLocation, m)
    for i in combVarious {
        var variousQueue: [VarousLocation] = i.map{ .init(i: $0.0, j: $0.1, count: 0, variousCount: 0, isVariousBlock: false) }
        var count = 0
        var visitedVariousMap: [[String]] = map.map { mapArr in
            return mapArr.map { block in
                if block == 1 {
                    return "-"
                } else if block == 2 {
                    return "*"
                }
                return "!"
            }
        }
        
        var visited: [[Bool]] = map.map { mapArr in
            return mapArr.map { block in
                if block == 1 {
                    return true
                }
                return false
            }
        }
        
        func checkAllDetect() -> Bool {
            for k in visitedVariousMap {
                if k.contains(where: { block in
                    return block == "!"
                }) {
                    return false
                }
            }
            return true
        }
        
        for various in variousQueue {
            visited[various.i][various.j] = true
            visitedVariousMap[various.i][various.j] = "0"
        }
        
        if checkAllDetect() {
            return 0
        }
        
        while !variousQueue.isEmpty {
            let popVarious = variousQueue.removeFirst()
            if !popVarious.isVariousBlock {
                visitedVariousMap[popVarious.i][popVarious.j] = "\(popVarious.variousCount)"
                count = max(count, popVarious.variousCount)
            } else {
                visitedVariousMap[popVarious.i][popVarious.j] = "\(popVarious.count)"
                count = max(count, popVarious.count)
            }
            for x in 0..<4 {
                let mi = popVarious.i+di[x]
                let mj = popVarious.j+dj[x]
                if mi >= n || mi < 0 || mj >= n || mj < 0 {
                    continue
                }
                if map[mi][mj] == 1 {
                    continue
                }
                if visited[mi][mj] {
                    continue
                }
                if popVarious.isVariousBlock {
                    if variousLocation.contains(where: { various in
                        if various.0 == mi && various.1 == mj {
                            return true
                        }
                        return false
                    }) {
                        variousQueue.append(.init(i: mi, j: mj, count: popVarious.count, variousCount: popVarious.variousCount+1, isVariousBlock: true))
                    } else {
                        variousQueue.append(.init(i: mi, j: mj, count: popVarious.variousCount+1, variousCount:  popVarious.variousCount+1, isVariousBlock: false))
                    }
                } else {
                    if variousLocation.contains(where: { various in
                        if various.0 == mi && various.1 == mj {
                            return true
                        }
                        return false
                    }) {
                        variousQueue.append(.init(i: mi, j: mj, count: popVarious.count, variousCount: popVarious.variousCount+1, isVariousBlock: true))
                    } else {
                        variousQueue.append(.init(i: mi, j: mj, count: popVarious.count+1, variousCount: popVarious.variousCount+1, isVariousBlock: false))
                    }
                }
                visited[mi][mj] = true
            }
        }
        
        
        
        
        if checkAllDetect() {
            answer = min(count, answer)
        }
    }
    return answer
}
var result = solution()
print(result == Int.max ? -1 : result)