[Swift][BFS][DFS] 백준 14502번 (연구소)

요구능력 : DFS와 BFS의 조합

 

코드설명 : 

 

우선, 이 문제에서 캐치해야할 중요한 요소가 2가지가 있다.

1. 바이러스는 퍼져나간다 (BFS)

2. 0인 빈 칸에 벽을 3개 세울 수 있다. n개에서 3개를 뽑는다는 말이다.

여기서 dfs를 써도 안전한지는 n과 m이 3<= n,m <= 8 이라는 문제의 조건을 보고 알 수 있다.

 

벽을 먼저 세워봅시다. 벽을 먼저 세우는 이유는 벽을 세워야 바이러스가 퍼지든말든 할거니까.

벽은 n과m 문제처럼 백트래킹 방식으로 모든 경우의 수를 세어볼것입니다.

무슨 말인지 모르겠다면 n과m 문제 시리즈를 먼저 풀고오는것을 강력권장합니다.(이거 풀려면 그냥 의무적으로 풀고오시길..)

백트래킹 방식으로 벽이 3개가 쌓였다면(depth = 3인경우) 이제 bfs()로 바이러스를 퍼뜨려줄것입니다.

 

bfs를 돌 때마다 벽 3개가 세워진 새로운 지도에 돌아야되므로

돌 때마다 방문처리도 새로해줘야하고 기존에 있는 지도(arr)를 건드리게되면 다음번 탐색이 불가능하니까 지도를 temp에 카피해줍니다.

그리고 카피한 지도를 돌면서 2가 있는 위치를 큐에 append(push)해줍니다.

2가 있는곳부터 바이러스가 퍼져야하기 때문입니다.

 

그리고 사방으로 탐색해주면서 0인곳을 2로 감염시켜줍니다.

이때, 사방으로 탐색해주는 이유는 만약 2가 1로 둘러쌓여있다면 사방을 탐색했을 때 0이 없어서 더이상 감염시키지 못하기 때문입니다.

 

그리고 queue가 비어서 탐색이 끝났다면(더이상 감염시킬 수 없다면) 0을 찾아서 세어줍니다.

 

참고로 백트래킹 하는부분에서 0부터 시작하지않고 이미 탐색한 부분은 탐색안하게 x의 시작좌표와 y의 시작좌표를 넣어주는게 더 좋은 알고리즘 이겠지만, 이렇게 문제가 풀리는걸 보아하니 이런식으로 풀어도 된다고 출제한 문제같아서 0부터 시작했습니다.

 

후기 :  문제에서 n과 m이 작으니까 완전탐색을 써야겠다! 라는걸 캐치못했어서 어려웠던거같다.

근데 진짜 좋은문제인듯.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = [[Int]]()

let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]
var result = 0
for _ in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

func dfs(_ depth: Int){
    if depth == 3{
        bfs()
        return
    }
    for i in 0..<n{
        for j in 0..<m{
            if arr[i][j] == 0{
                arr[i][j] = 1
                dfs(depth + 1)
                arr[i][j] = 0
            }
        }
    }
    
}

func bfs(){
    var visited = Array(repeating: Array(repeating: false, count: 9), count: 9)
    var temp = arr
    var queue = [Int]()
    for i in 0..<n{
        for j in 0..<m{
            if temp[i][j] == 2 {
                queue.append(i * 10 + j)
            }
        }
    }
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        let x = pop / 10
        let y = pop % 10
        for i in 0..<4{
            let nx = x + dx[i]
            let ny = y + dy[i]
            if nx >= 0 && nx < n && ny >= 0 && ny < m{
                if temp[nx][ny] == 0 && !visited[nx][ny]{
                    visited[nx][ny] = true
                    temp[nx][ny] = 2
                    queue.append(nx * 10 + ny)
                }
                
            }
        }
    }
    var count = 0
    for i in 0..<n{
        for j in 0..<m{
            if temp[i][j] == 0{
                count += 1
            }
        }
    }
    result = max(result, count)
}

dfs(0)

print(result)