[Algorithm] 백준 - 14502번 연구소 (Swift)

문제 소개

https://www.acmicpc.net/problem/14502
연구소에 바이러스가 퍼지지 않게 하는 문제!

문제 풀이

벽은 dfs를 활용하여 모든 map의 경우를 만들어 준 후, bfs를 활용해서 바이러스를 전파(?)시켜서 최솟값을 구했다. 좀더 구현에 가까운 문제였던듯 싶다.

import Foundation

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
let ds = [(1, 0), (-1, 0), (0, 1), (0, -1)]

var map = [[Int]]()
var queue = [(Int, Int)]()

for i in 0..<n {
    let line = readLine()!.split(separator: " ").map { Int($0)! }
    map.append(line)

    for j in 0..<m {
        if line[j] == 2 {
            queue.append((i, j))
        }
    }
}

func getCount(_ map: [[Int]]) -> Int {
    var queue = queue
    var map = map
    var idx = 0

    while queue.count > idx {
        let poped = queue[idx]
        idx += 1
        
        for d in ds {
            let i = poped.0 + d.0
            let j = poped.1 + d.1
            
            if 0..<n ~= i && 0..<m ~= j {
                if map[poped.0][poped.1] == 2 && map[i][j] == 0 {
                    map[i][j] = 2
                    queue.append((i, j))
                }
            }
        }
    }

    var cnt = 0

    for i in 0..<n {
        for j in 0..<m {
            if map[i][j] == 0 {
                cnt += 1
            }
        }
    }
    
    return cnt
}

var maxCount = 0

func dfs(_ depth: Int) {
    if depth == 3 {
        maxCount = max(maxCount, getCount(map))
        return
    }
    
    for i in 0..<n {
        for j in 0..<m {
            if map[i][j] == 0 {
                map[i][j] = 1
                dfs(depth + 1)
                map[i][j] = 0
            }
        }
    }
}

dfs(0)
print(maxCount)