[백준] 14502번 연구소 [Swift]

문제 링크

14502번: 연구소

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1 ×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈칸의 개수는 3개 이상이다.

출력

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

문제 풀이

이 문제에서 중요한 것은 벽을 3개만 세울 수 있다는 점입니다.

근데 처음 문제를 읽었을 때 어떻게 3개를 세우는 게 효율적 일지 생각하다가.. 그냥 완전 탐색으로 모두 하는 게 쉬워 보여서 그렇게 했습니다.

실제로 입력값의 크기도 크지 않기 때문에 완전탐색으로 3개의 벽을 세우기로 했습니다.

3개의 벽을 세울 지점을 골랐다면 벽이 있다는 표시를 해주고 (0을 1로 바꿉니다) 그런 뒤 바이러스가 있는 지점으로부터 bfs를 수행해서 바이러스를 퍼뜨리면 됩니다.

모든 경우를 해보고 가장 안전 영역이 많을 때를 기억했다가 나중에 출력하면 됩니다.

즉 정리하면 이러한 방식입니다.

 

1. 3개의 벽을 세울 지점을 선택합니다.

2. 3개의 벽을 세웁니다.

3. 바이러스를 퍼뜨립니다. (bfs 사용)

4. 바이러스를 모두 퍼뜨린 뒤 안전 영역의 개수를 셉니다.

5. 안전 영역의 최대 개수를 가진 값을 출력합니다.

소스 코드

import Foundation
class Queue<T>{
    var enqueue: [T]
    var dequeue: [T] = []
    
    var isEmpty: Bool{
        return enqueue.isEmpty && dequeue.isEmpty
    }
    var count: Int{
        return enqueue.count + dequeue.count
    }
    
    init(_ queue:[T]){
        self.enqueue = queue
    }
    
    func push(_ n: T){
        enqueue.append(n)
    }
    
    func pop() -> T?{
        if dequeue.isEmpty{
            dequeue = enqueue.reversed()
            enqueue.removeAll()
        }
        return dequeue.popLast()
    }
    
}
func solution() {
    let firstLine = readLine()!.split(separator: " ").map({Int(String($0))!})
    let n = firstLine[0]
    let m = firstLine[1]
    
    var map: [[Int]] = []
    var safeArea: [[Int]] = []
    var virusArea: [[Int]] = []
    
    for _ in 0..<n{
        map.append(readLine()!.split(separator: " ").map({Int(String($0))!}))
    }
    
    // 안전영역의 좌표를 구한다.
    // 바이러스 좌표 구한다.
    for i in 0..<map.count {
        for j in 0..<map[i].count {
            if map[i][j] == 0 {
                safeArea.append([i,j])
            } else if map[i][j] == 2 {
                virusArea.append([i,j])
            }
        }
    }
    
    var result: Int = 0

    let dx: [Int] = [0,0,-1,1]
    let dy: [Int] = [-1,1,0,0]
    
    
    // 3개의 벽을 만들고 바이러스를 퍼뜨리는 함수
    func makeWall(map: [[Int]]){
        var map = map
        
        let queue = Queue(virusArea)
        while !queue.isEmpty {
            guard let now = queue.pop() else { fatalError() }
            
            for i in 0..<dx.count {
                let nextX = now[1] + dx[i]
                let nextY = now[0] + dy[i]
                
                if nextX < 0 || nextY < 0 || nextX > m-1 || nextY > n-1 {
                    continue
                } else {
                    if map[nextY][nextX] == 0 {
                        map[nextY][nextX] = 2
                        queue.push([nextY, nextX])
                    }
                }
            }
        }
        var temp = 0
        for i in 0..<n {
            for j in map[i] {
                if j == 0 {
                    temp += 1
                }
            }
        }
        if result < temp {
            result = temp
        }
    }
    
    // 빈 벽 3개를 구하는 것
    func findThreeWalls() {
        for i in 0..<safeArea.count {
            for j in i+1..<safeArea.count {
                for k in j+1..<safeArea.count {
                    var map = map
                    let point1 = safeArea[i]
                    let point2 = safeArea[j]
                    let point3 = safeArea[k]
                    
                    map[point1[0]][point1[1]] = 1
                    map[point2[0]][point2[1]] = 1
                    map[point3[0]][point3[1]] = 1
                    
                    makeWall(map: map)
                }
            }
        }
    }
    
    findThreeWalls()

    print(result)
}

solution()