[백준] 연구소 (14502)

문제 설명

백준 14502번 문제 링크

입력 및 출력

» 입력

• 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8) 둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다. 빈 칸의 개수는 3개 이상이다.

» 출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제 입출력(테스트케이스)

입력	출력
7 7 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0	27
4 6 0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2	9
8 8 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	3

문제 풀이(SWIFT) 1

//
//  main.swift
//  BOJ14502_SWIFT
//
//  Created by choiyoujun on 2022/03/10.
//

var ans = 0
let xy = readLine()!.split(separator: " ").map { Int($0)! }
let X = xy[1]
let Y = xy[0]
var map = [[Int]](repeating: [Int](repeating: 0, count: X), count: Y)

for y in 0..<Y {
    map[y] = readLine()!.split(separator: " ").map { Int($0)! }
}

func createWalls(depth: Int) {
    if depth == 3 {
        spreadViruses()
        return
    }
    
    for i in 0..<Y {
        for j in 0..<X {
            if map[i][j] == 0 {
                map[i][j] = 1
                createWalls(depth: depth + 1)
                map[i][j] = 0
            }
        }
    }
}

func spreadViruses() {
    let dx = [0, 1, 0, -1]
    let dy = [1, 0, -1, 0]
    var tempMap = map
    var q = [(x: Int, y: Int)]()
    
    for y in 0..<Y {
        for x in 0..<X {
            if tempMap[y][x] == 2 {
                q.append((x, y))
            }
        }
    }
    
    while !q.isEmpty {
        let virus = q.removeFirst()
        
        for i in 0..<4 {
            let nx = dx[i] + virus.x
            let ny = dy[i] + virus.y
            
            if (0..<X).contains(nx) && (0..<Y).contains(ny) {
                if tempMap[ny][nx] == 0 {
                    tempMap[ny][nx] = 2
                    q.append((nx, ny))
                }
            }
        }
    }
    
    caculateSafes(resMap: &tempMap)
}

func caculateSafes(resMap: inout [[Int]]) {
    var count = 0
    
    for y in 0..<Y {
        for x in 0..<X {
            if resMap[y][x] == 0 { count += 1 }
        }
    }
    
    ans = max(ans, count)
}

createWalls(depth: 0)
print(ans)