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

요구능력 : 백트래킹을 통한 BFS

 

코드설명 : 

 

바이러스가 퍼질 수 있는 위치들이 주어졌다.

이 위치중에서 m개를 골라서 바이러스를 넣고 퍼뜨려야한다.

여기서 바이러스가 퍼질 수 있는 위치(2가 들어 있는 위치)를 먼저 구해서 튜플형태로 배열에 전부 저장해줬다.

그리고 m개를 고르기 위해서 백트래킹을 사용하였다.

 

백트래킹으로 m개 고른 위치를 bfs에 넣고 bfs로 바이러스를 퍼뜨려준다.

check함수를 통해서 벽이아닌데 방문하지않은곳이 있으면 모든 빈칸에 바이러스를 퍼뜨릴 수 없는경우이므로 Int.max를 넣어주고 마지막에도 값이 Int.max라면 결국, 모든 빈칸에 바이러스를 퍼뜨릴 수 없는것이라 -1을 출력해준다.

 

내 마음대로 설명하는 순열과 조합

순열은 {0, 1, 2, 3}이 있으면 순서를 고려하여 모든 경우의 수를 찾는다.

ex) {0, 1, 2, 3}과 {1, 0, 2, 3}은 다른것이다.

 

조합은 {0, 1, 2, 3}이 있으면 순서를 고려하지 않는다.

ex) {0, 1, 2, 3}과 {1, 0, 2, 3}은 같은것이다. 같은수가 다 들어있기 때문에.

 

순열과 조합을 이해하는데는 N과 M시리즈만한게 없는거같다.

 

후기 : 처음에 순열로 풀었다가 시간초과나서 멘탈에 금이갔었..는데 조합으로 바꾸니까 바로풀렸다..

결론은 시간초과를 해결했다.

let nm = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = nm[0]
let m = nm[1]
var arr = [[Int]]()
var virusLocation = [(Int, Int)]() //바이러스의 전체위치
var storeVirusLocation = [(Int, Int)]() //dfs에서 저장해서 옮길 바이러스 m개의 위치
var printValue = Int.max
for i in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    for j in 0..<n{
        if arr[i][j] == 2{
            virusLocation.append((i, j))
        }

    }
}

var visitedDFS = Array(repeating: false, count: virusLocation.count)
func dfs(_ depth: Int, _ start: Int){
    if depth == m{
        printValue = min(printValue, bfs(storeVirusLocation))
        return
    }
    for i in start..<virusLocation.count{
        if !visitedDFS[i]{
            visitedDFS[i] = true
            storeVirusLocation.append(virusLocation[i])
            dfs(depth + 1, i)
            visitedDFS[i] = false
            storeVirusLocation.removeLast()
        }
    }

}

func bfs(_ realVirusLocation: [(Int, Int)]) -> Int{
    var visited = Array(repeating: Array(repeating: false, count: n), count: n)
    let dx = [-1, 1, 0, 0]
    let dy = [0, 0, -1, 1]
    var time = 0
    var queue = [((Int, Int), Int)]()//x좌표, y좌표, 최소시간

    for i in 0..<m{
        queue.append(((realVirusLocation[i].0,realVirusLocation[i].1), 0))
        visited[realVirusLocation[i].0][realVirusLocation[i].1] = true
    }

    var idx = 0
    while queue.count > idx{
        let pop = queue[idx]
        idx += 1
        let x = pop.0.0
        let y = pop.0.1
        time = pop.1
        for i in 0..<4{
            let nx = x + dx[i]
            let ny = y + dy[i]
            if nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] { continue }
            if arr[nx][ny] == 1{
                visited[nx][ny] = true
                continue
            }

            queue.append(((nx, ny), pop.1 + 1))
            visited[nx][ny] = true
        }
    }
    if check(visited){
        return time
    }else{
        return Int.max
    }
}

func check(_ visited: [[Bool]]) -> Bool{
    for i in 0..<n{
        for j in 0..<n{
            if !visited[i][j] && arr[i][j] != 1{
                return false
            }
        }
    }
    return true
}

dfs(0, 0)
if printValue == Int.max{
    print(-1)
}else{
    print(printValue)
}