[Swift][DFS][BFS] 백준 17142 (연구소 3)

요구능력 : 백트래킹과 BFS

 

코드설명 : 

 

연구소 2 문제를 안풀었다면 먼저 풀고오는게 맞는거같다.

 

연구소2 문제와 다른점만 설명하고 넘어가겠다.

연구소2 같은경우에는 선택되지 않은 바이러스는 그냥 빈칸처럼 사용했다.

연구소3 에서는 비활성바이러스를 활성바이러스로 바꾸기위해서 해당 바이러스를 활성화해서 큐에 넣어야한다.

그런데 어려워보이고 정답비율이 낮은이유가 "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다."

위 설명 때문이다.

말이 어렵지 그냥 빈칸없으면 정답이된다.

 

왜?

핵심적으로 봐야될 부분은 "활성바이러스가 비활성 바이러스가 있는 칸으로 간다."는 것이다.

그럼 활성바이러스가 비활성바이러스로 갈 때는 결국 세줘야한다.

 

빈칸처럼 쓰는거랑 그럼 차이점이 뭐냐?

연구소2 문제처럼 바이러스가 있는곳을 빈칸처럼 쓰게되면 바이러스가 있는 위치인 2마저 0(빈칸)으로봐야한다.

하지만 이 문제에서는 2를 따로 0으로 생각하지않고 전체빈칸인 0의 개수에 대해서만 신경을 써주면 된다.

이렇게 되면 자동적으로 문제에서 요구하는 비활성바이러스가 활성바이러스로 변하는것이다.

 

나는 이렇게 이해했다.

어차피 비활성이 활성으로변해도 걸리는 시간은 똑같다.

만약 비활성까지 오는데 걸린시간이 3이다.

그럼 비활성-> 활성으로 변한 바이러스가 다음 빈칸으로 가는 시간은? 그렇다. 4이다.

보면 셈은 똑같이된다.

 

결론 : 연구소2에서는 바이러스까지 빈칸으로 세야하지만, 연구소 3에서는 바이러스는 바이러스로 보고 빈칸은 빈칸으로 보기때문에, queue에 바이러스가 남아있더라도 돌 필요가 없다.

빈칸만 다돌면 끝나기때문이다.

그렇게되면 세는건 똑같지만 연구소2와 같은 테스트케이스를 넣어도 수가 다르게 나오는것이다.

 

후기 : 문제이해가 어려웠던것같다.

알고보면 그저 조합과 너비우선탐색을 섞기만한 문제..?

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

var arr = [[Int]]()
var inActiveVirusLoc = [(Int, Int)]()
var emptyCount = 0
for i in 0..<n{
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
    for j in 0..<n{
        if arr[i][j] == 2{
            inActiveVirusLoc.append((i, j))
        }
        if arr[i][j] == 0{
            emptyCount += 1 //빈 공간 셀 변수
        }
        
    }
}
var dfsVisited = Array(repeating: false, count: inActiveVirusLoc.count)
var activeVirus = [(Int, Int)]()
var result = Int.max
func dfs(_ depth: Int, _ start: Int){
    
    if depth == m{
        result = min(result, bfs(activeVirus))
        return
    }
    for i in start..<inActiveVirusLoc.count{
        if !dfsVisited[i]{
            dfsVisited[i] = true
            activeVirus.append(inActiveVirusLoc[i])
            dfs(depth + 1, i)
            activeVirus.removeLast()
            dfsVisited[i] = false
        }
    }
}

let dx = [-1, 1, 0, 0]
let dy = [0, 0, 1, -1]

func bfs(_ virus: [(Int, Int)]) -> Int{
    var time = 0
    var cnt = emptyCount//남아있는 공간 셀 변수
    var queue = [((Int, Int), Int)]()//x좌표, y좌표, 퍼뜨리는 시간
    var visited = Array(repeating: Array(repeating: false, count: n), count: n)

    for i in 0..<m{
        queue.append(((virus[i].0, virus[i].1), 0))
        visited[virus[i].0][virus[i].1] = true
    }
    while !queue.isEmpty{
        let pop = queue.removeFirst()
        let x = pop.0.0
        let y = pop.0.1
        time = pop.1
       
        if arr[x][y] == 0 {
            cnt -= 1
        }
        if cnt == 0 {
            return time
        }
        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{continue}
            queue.append(((nx, ny), time + 1))
            visited[nx][ny] = true
                        
        }
        
    }
    return Int.max
}
dfs(0, 0)
if result == Int.max{
    print(-1)
}else{
    print(result)
}