백준 2638번 치즈 - 스위프트(Swift) 풀이 + 그림 설명

1. 가장자리 아무 칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다.
2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다.
3. 치즈가 남지 않을 때까지 1-2를 반복한다.

---

1. 가장자리 아무칸에서나 시작해 DFS/BFS로 인접한 모든 칸들을 외부 공기 처리한다.

 가장자리에는 치즈가 오지 않으므로 항상 외부 공기가 있는 칸이다. 치즈로 둘러싸여 있는 내부 공기 칸과 구분하기 위해 매시간마다 가장자리에서 시작하는 BFS/DFS를 돌면서 인접한 칸들을 모두 외부 공기 칸으로 처리해준다.

 좌측과 같은 초기 상황이라고 하면, 먼저 우측 그림처럼 외부 공기 처리를 해준다. 내부 공기와는 다르게 처리되고 있는 것에 유의한다. 

 

2. 치즈들을 모두 순회하면서 녹을지 말지를 결정한다.

 매 시간마다 녹아야하는 치즈들을 처리해야 한다. 모든 치즈들을 순회하면서 인접한 4개 칸 중 2개 이상이 외부 공기칸인지 체크한다. 만약 그렇다면 치즈가 없는 칸(흰색)으로 바꾸어준다.

 

3. 치즈가 남지 않을 때까지 1-2를 반복한다.

 다시 1로 돌아가서 외부 공기 처리를 해준다. 내부 공기였다가 외부 공기로 바뀌었을 수 있기 때문이다. 이제 다시 남은 치즈에 대해서 2번을 반복하면 된다.

 

 시간복잡도는 DFS/BFS에 O(NM)이 들고, 최대 NM시간이 걸릴 수 있으므로 O(N^2 * M^2)이 된다. N, M이 최대 100이므로 최대 10^8번의 연산이 이루어지기 때문에 제한 시간 내에 통과될 수 있다.

 

---

import Foundation

let cheese = 1, noCheese = 0, air = -1
var N = 0, M = 0
var arr = Array(repeating: [Int](), count: 100)
var visit = [[Bool]]()

func DFS(row: Int, col: Int) {
    visit[row][col] = true
    arr[row][col] = air
    
    let adjacents = [(row+1, col), (row-1, col), (row, col+1), (row, col-1)].filter {
        (0..<N) ~= $0.0 && (0..<M) ~= $0.1
    }
    
    for adj in adjacents {
        let adjRow = adj.0
        let adjCol = adj.1
        
        guard !visit[adjRow][adjCol] && arr[adjRow][adjCol] != cheese else { continue }
        DFS(row: adjRow, col: adjCol)
    }
}

func contactWithAir() {
    visit = Array(repeating: Array(repeating: false, count: 100), count: 100)
    DFS(row: 0, col: 0)
}

func meltCheese() {
    for row in 0..<N {
        for col in 0..<M {
            guard arr[row][col] == cheese else { continue }
            
            let adjacents =  [(row+1, col), (row-1, col), (row, col+1), (row, col-1)].filter {
                (0..<N) ~= $0.0 && (0..<M) ~= $0.1
            }
            let adjacentsAir = adjacents.filter { arr[$0.0][$0.1] == air }
            
            if adjacentsAir.count >= 2 { arr[row][col] = noCheese }
        }
    }
}

func checkNoMoreCheese() -> Bool {
    for i in 0..<N {
        for j in 0..<M {
            if arr[i][j] == cheese { return false }
        }
    }
    
    return true
}

func solution() {
    let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
    N = input[0]
    M = input[1]
    
    for i in 0..<N {
        arr[i] = readLine()!.split(separator: " ").map{ Int(String($0))! }
    }
    
    var count = 0
    
    while !checkNoMoreCheese() {
        contactWithAir()
        meltCheese()
        
        count += 1
    }
    
    print(count)
}

solution()