백준 14502번 연구소 (swift) [G1]

BFS

큐로 BFS를 구현했다.

생각 회로

• 무작위 세 점을 선택해서 ( 1보다 큰 점은 안 된다. == 0만 가능)
• 그 점에 벽을 세우고 BFS로 탐색 ( 2가 전염시킨다. )
• 모든 점을 탐색하면서, Clean한 영역의 개수의 최댓값 탐색 ( N, M <= 8이라서 시간적으로 자유롭다.)

주의사항

• 제네릭한 큐 구현이 가장 힘들었다.
• 무작위 세 점 선택하기
• 설명은 쉬운데, 코드가 길어서 주석은 없다.

class Queue<T>{
    var enq = [T]()
    var deq = [T]()
    
    init(_ queue:[T]){
        self.enq = queue
    }

    var count: Int{
        return enq.count + deq.count
    }
    func push(a:T){
        enq.append(a)
    }
    func pop()-> T?{
        if deq.isEmpty{
            deq = enq.reversed()
            enq.removeAll()
        }
    
        return deq.removeLast()
    }
}
let input = readLine()!.split(separator: " ").map{Int(String($0))!}

let n = input[0]
let m = input[1]

var li = [[Int]]()
for _ in 0..<n{
    li.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}


let ix = [0,0,1,-1]
let iy = [1,-1,0,0]

var q:Queue = Queue([])

for i in 0..<n{
    for j in 0..<m{
        if li[i][j] == 2{
            q.push(a: [i,j])
        }
    }
}

let qsave = Queue([])
qsave.deq = q.deq
qsave.enq = q.enq
var clean = 0
var liSafe = li


func findClean()->Int{
    while q.count != 0{
        for _ in 0..<q.count{
            guard let poison = q.pop() as? [Int] else { fatalError() }
            
            for k in 0..<4{
                let row = poison[0] + ix[k]
                let col = poison[1] + iy[k]
                
                if row < 0 || col < 0 || row >= n || col >= m{
                    continue
                }
                if li[row][col] == 0{
                    li[row][col] = 2
                    q.push(a: [row,col])
                }
            }
        }
    }
    var ret = 0
    for i in 0..<n{
        for j in 0..<m{
            if li[i][j] == 0{
                ret = ret + 1
            }
        }
    }
    return ret
}

for i in 0..<n*m{
    for j in i+1..<n*m{
        for k in j+1..<n*m{
            if li[i/m][i%m] >= 1 || li[j/m][j%m] >= 1 || li[k/m][k%m] >= 1{
                continue
            }
//            print("\(i/m),\(i%m) \(j/m),\(j%m) \(k/m),\(k%m)")
            
            li[i/m][i%m] = 1
            li[j/m][j%m] = 1
            li[k/m][k%m] = 1
            
            let hubo = findClean()
            
            if clean < hubo{
                clean = hubo
            }
            li = liSafe
            q.deq = qsave.deq
            q.enq = qsave.enq
        }
    }
}
print(clean)