[백준/Swift] 17142번: 연구소 3

 

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

17142번: 연구소 3

 

 

구현 흐름

1. 바이러스 중 M개 활성화 → 조합 경우 구하기(중복 없이)

   → 바이러스 정보를 viruses 배열에 넣고 (튜플 형태) M개 고르기 (choice 배열에 따로 넣어줌)

2. 바이러스 퍼트리기 → BFS 탐색 후, max 값 구하기

---

코드 설명

1. 전처리

    viruses 배열에 바이러스 정보(x, y) 넣기

    벽은 “-”로 바꾸기

    

2. 모든 조합의 경우의 수마다 BFS 탐색

    바이러스 중 M개 선택하기   

    M개의 바이러스(choice 배열)로 BFS 돌리기

 

    -  전처리

         선택된 바이러스를 동시에 퍼트리기 위해 모두 queue에 넣어주기

         활성화된 바이러스는 “0”, 비활성화 바이러스는 “*” 로 업데이트

   (1) 방문하지 않은 곳이고 빈칸이라면 이전 방문 시간 + 1 할당

         maxValue 업데이트 (이 변수는 최대 시간 출력하기 위해 있음)

         queue에 넣어줌

   (2) 비활성화 바이러스인 칸이라면 이전 방문 시간 + 1 할당

         → 비활성화된 바이러스는 0(빈칸)이자 1(벽). 즉, 통과할 수 있는 곳이지만 감염시킬 필요가 없는 곳임…

         queue에 넣어줌 → 다음 칸으로 넘어가야 하므로

  ⭐️ 이전 방문 시간 + 1을 하는 이유는, 이 칸을 방문했기 때문에 시간이 갔기 때문! 대신, maxValue는 업데이트하지 않는다.

        여기는 지나가는 곳이기 때문

 

    바이러스가 퍼지지 않은 곳(”0”)이 있다면 Int.max 넣어줌

 

4. 최소 시간을 담은 answer가 Int.max라면 바이러스를 모두 퍼트릴 수 있는 방법이 없는 것이므로 -1 출력 아니면 최소 시간 출력

 

import Foundation

//input
let nm = readLine()!.split(separator: " ").map{ Int(String($0))! }
var array = [[String]]()
for _ in 0..<nm[0] {
    array.append(readLine()!.split(separator: " ").map{ String($0) })
}

var viruses = [(Int, Int)]()
var choice = [(Int, Int)]()
var answer = Int.max

//1
for i in 0..<nm[0] {
    for j in 0..<nm[0] {
        if array[i][j] == "2" {
            viruses.append((i, j))
        }else if array[i][j] == "1" {
            array[i][j] = "-"
        }
    }
}
var visited = [Bool](repeating: false, count: viruses.count+1)

//3. 바이러스 퍼트리기 -> 가장 오래 걸린 시간 찾아서 answer에 넣기
func spreadVirus() -> Int {
    var temp = array
    let direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    var queue = [(Int, Int)]()
    var front = 0
    var maxValue = 0
    //선택한 모든 바이러스 동시에 탐색 시작해야하므로 모두 queue에 넣어준다.
    viruses.forEach { virus in
        if choice.contains(where: { (x, y) in
            return x == virus.0 && y == virus.1
        }) {
            queue.append((virus.0, virus.1))
            temp[virus.0][virus.1] = "V" //활성화된 바이러스들은 "0"으로
        }else {
            temp[virus.0][virus.1] = "*" //얘는 비활성화 바이러스로, 여기는 그냥 냅둔다
        }
    }
    while queue.count > front {
        let(x, y) = queue[front]
        front += 1
        
        for i in 0..<4 {
            let dx = x + direction[i][0]
            let dy = y + direction[i][1]
            
            guard (0..<nm[0]) ~= dx, (0..<nm[0]) ~= dy else { continue } //범위 벗어난 경우
            //값이 "0" -> 빈 칸/방문안했다는 의미
            if temp[dx][dy] == "0" {
                temp[dx][dy] = String((Int(temp[x][y]) ?? 0) + 1)
                maxValue = max(maxValue, Int(temp[dx][dy])!)
                queue.append((dx, dy))
            }
            if temp[dx][dy] == "*" { //비활성화된 애라면
                temp[dx][dy] = String((Int(temp[x][y]) ?? 0) + 1)
                queue.append((dx, dy))
            }
        }
    }
    if temp.contains(where: { tmp in
        return tmp.contains(where: {$0 == "0"})
    }) {
        maxValue = Int.max
    }
    return maxValue
}

//2. 모든 바이러스 중 M개 바이러스 활성화 (경우의 수 -> BT)
//조합 -> N개 중 M개를 중복없이 고르기
func chooseVirus(_ k: Int, _ s: Int) {
    if k == nm[1] { //m개 모두 골랐음 -> BFS로 바이러스 퍼트리기
        answer = min(answer, spreadVirus())
        return
    }
    
    for i in s..<viruses.count {
        if !visited[i] {
            visited[i] = true
            choice.append(viruses[i])
            chooseVirus(k+1, i+1)
            choice.removeLast()
            visited[i] = false
        }
    }
}

chooseVirus(0, 0)
print(answer == Int.max ? -1 : answer)

 

 

→ 틀린 이유는 비활성화 바이러스를 고려하지 않았기 때문! 첫 번째 실패는 81%쯤에서 발생.. 비활성화 바이러스… 이런 반례를 대체 어떻게 찾아서 하는 거야…!! 반례 찾기가 제일 어렵다…