[Swift] 백준_연구소(14502)

문제

 

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

 

풀이

 

처음에는 벽을 어디에 세워야 바이러스가 최소한으로 퍼질지 고민을 오래했다. 근데 벽의 개수가 반드시 3개이고 n과 m이 큰 숫자도 아니기때문에 일단 모든 경우를 구해보기로 했다.

 

우선, 0인 위치를 전부 찾아서 3개로 만들 수 있는 모든 조합을 구했다.

 

다음으로 각 조합별로 실제로 벽을 세워 각각 BFS를 돌려 확인했다.

 

각 경우마다 안전범위를 구하는 것은 직접 하나하나 확인하지 않고, 처음에 구했던 zeros의 count에서 3을 뺀 것이 처음의 안전범위이므로 이 값에서 queue의 count를 빼주었다.

근데 주의해야 할 것은 queue에는 바이러스가 퍼진 위치들이 전부 들어있음과 동시에 처음에 구했던 바이러스(virus)도 들어있기때문에 virus의 count를 더해주어야 결과를 출력할 수 있다.

import Foundation

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = input[0]
let m = input[1]
var lab: [[Int]] = []
for _ in 0..<n {
    lab.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}
let dx = [1,0,-1,0]
let dy = [0,1,0,-1]
var zeros: [[Int]] = []
var virus: [[Int]] = []
var result: [Int] = []
for i in 0..<n {
    for j in 0..<m {
        if lab[i][j] == 0 {
            zeros.append([i,j])
        } else if lab[i][j] == 2 {
            virus.append([i,j])
        }
    }
}
var temp: [[[Int]]] = []
for i in 0..<zeros.count {
    for j in i + 1..<zeros.count {
        for k in j + 1..<zeros.count {
            temp.append([zeros[i],zeros[j],zeros[k]])
        }
    }
}
for combi in temp {
    var newLab = lab
    for point in combi {
        newLab[point[0]][point[1]] = 1
    }
    var queue = virus
    var idx = 0
    while idx < queue.count {
        let current = queue[idx]
        idx += 1
        for i in 0..<dx.count {
            let newX = current[0] + dx[i]
            let newY = current[1] + dy[i]
            if newX < 0 || newY < 0 || newX >= n || newY >= m {
                continue
            }
            if newLab[newX][newY] == 1 || newLab[newX][newY] == 2 {
                continue
            }
            newLab[newX][newY] = 2
            queue.append([newX,newY])
        }
    }
    result.append(zeros.count - 3 - queue.count + virus.count)
}
print(result.max()!)

 

 

_____________________________________________________________________________________________________

 

 

일단 풀어보자는 마인드가 쉽지 않다. 아무래도 시간을 재서 풀어봐야할듯