[swift] 백준 - 2606번: 바이러스

2606번: 바이러스

---

나의 풀이

let computerCount = Int(readLine()!)!
let networkCount = Int(readLine()!)!
var network = Array(repeating: [Int](), count: computerCount+1)
var virus = [1]
var result = [Int]()
for _ in 0..<networkCount {
    let i = readLine()!.split(separator: " ").map { Int($0)! }
    network[i[0]].append(i[1])
    network[i[1]].append(i[0])
}
while !virus.isEmpty {
    let pop = virus.popLast()!
    for i in network[pop] {
        if !result.contains(i) && !virus.contains(i) { virus.append(i) }
    }
    result.append(pop)
}
print(result.count-1)

풀이 키워드

DFS(깊이 우선 탐색)
virus는 노드 1에서부터 퍼져 나갑니다.
virus배열을 만들어 1을 넣고
virus가 비워질 때까지 while문을 실행시킵니다.
virus의 마지막 요소를 pop 시키면 처음 있던 노드 1이 지워지며
변수 pop에 담아 pop(1)에 해당하는 네트워크가 가리키고 있는
노드를 virus에 담습니다.
과정속에서 중복을 지우기 위해 result에 포함되지 않거나, virus에 포함되지 않은 노드만 virus에 담아줬습니다.
반복이 끝난 노드는 result에 담아 방문표시(바이러스에 걸림)를 해줍니다.

주의할 점은 바이러스는 앞, 뒤 모두 퍼져나갈 수 있다는 것입니다.
따라서 5 노드는 8을 가리키고 8 노드는 1 노드를 가리키고 있다면
1 노드에 연결된 8 노드도 감염되고, 8 노드를 가리키고 있는 5 노드도 감염됩니다.

 

---