Swift - 백준 2606번

바이러스 문제는 DFS 또는 BFS 를 사용하여 해결할 수 있습니다

 

 

DFS를 구현하기 위해서는 재귀함수를 구현해야 합니다. 이전에 값들을 저장하기 위해서 visited 배열을 만들었습니다.

 

예제 입력 1

7
6
1 2
2 3
1 5
5 2
5 6
4 7

 

예제 출력 2

4

 

풀이

풀이를 해보면 바이러스 노드를 직접 구해봅니다.

 

1: 2 5

2: 1 3 5

3: 2

4: 7

5: 1 2 6

6: 5

7: 4

 

DFS는 계속해서 파고파고 들어가는 것이기 때문에 1 -> 2 -> 3 -> 5 -> 6 이므로 1 컴퓨터는 총 4대의 컴퓨터를 감염시켰습니다.

이제 위에 DFS를 직접 구현하여 해결하는 코드입니다.

import Foundation

let n = Int(readLine()!)!
let m = Int(readLine()!)!


if m <= 0 {
    print(0)
    exit(0)
}

var arr: [[Int]] = .init(repeating: .init(repeating: 0, count: n+1), count: n+1)

for _ in 1...m {
    let tmp = readLine()!.split(separator: " ").map { Int($0)! }
    arr[tmp[0]].append(tmp[1])
    arr[tmp[1]].append(tmp[0])
}


var visited: [Bool] = .init(repeating: false, count: n+1)
var count = 0
func dfs(m: Int) {
    visited[m] = true
    
    for i in arr[m] {
        if !visited[i] {
            count+=1
            dfs(m: i)
        }
    }
    
}
dfs(m: 1)
print(count >= 1 ? count-1 : 0)