[코딩테스트] 🦠 연구소 - 백준14502

문제링크

난이도

골드 4

유형

구현

소요시간

1시간

회고

BFS + 조합 + 작은 가지치기

코드

// 1. 맵 리딩
// 1) 바이러스 수집
// 2) 벽 수집

let nm = readLine()!.split(separator: " ").compactMap { Int($0) }
let (N, M) = (nm[0], nm[1])

var board = Array(repeating: Array(repeating: 0, count: M), count: N)
var virus: [(Int, Int)] = []
var wall: [(Int, Int)] = []
var blanks: [(Int, Int)] = []

(0..<N).forEach { r in
    let row = readLine()!.split(separator: " ").compactMap { Int($0) }
    board[r] = row
    (0..<M).forEach { c in
        if row[c] == 2 {
            virus.append( (r, c) )
        } else if row[c] == 1 {
            wall.append( (r, c))
        } else {
            blanks.append((r, c))
        }
    }
}

// 2. 벽 세우기 조합

let dr = [-1, 0, 1, 0]
let dc = [0, 1, 0, -1]

func calculate(selected: [Int]) -> Int {
    var next = board

    let (r1, c1) = blanks[selected[0]]
    let (r2, c2) = blanks[selected[1]]
    let (r3, c3) = blanks[selected[2]]

    next[r1][c1] = 1
    next[r2][c2] = 1
    next[r3][c3] = 1

    var safe = blanks.count - 3

    var q = virus
    var head = 0

    while head < q.count {
        let (r, c) = q[head]
        head += 1

        for k in (0..<4) {
            let nr = r + dr[k]
            let nc = c + dc[k]

            if (0..<N) ~= nr && (0..<M) ~= nc && next[nr][nc] == 0 {
                safe -= 1
                next[nr][nc] = 2
                q.append((nr, nc))

                if safe <= best { return -1 }
            }
        }
    }

    return safe
}

var best = 0

var selected: [Int] = []

// 벽 조합 생성
// 시뮬레이션

// 4. 안전 지대 0 갯수 세기

func combi(_ depth: Int = 0, _ start: Int = 0) {
    if selected.count == 3 {
        best = max(best, calculate(selected: selected))
        return
    }

    if start >= blanks.count { return }

    for i in start..<blanks.count {
        selected.append(i)
        combi(depth + 1, i + 1)
        selected.removeLast()
    }
}

combi(0, 0)
print(best)