[알고리즘] Swift -백준 #2606(바이러스) -DFS/BFS

문제링크

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

 

 

---

분석

한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸린다.

네트워크가 연결되어있지 않으면 영향을 받지 않는다.

1번 컴퓨터가 웜 바이러스에 걸렸을 때 걸리게 되는 컴퓨터의 수를 출력하라

 

풀이 과정

첫째 줄 = 컴퓨터의 수

둘째 줄 = 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수

둘째 줄의 수만큼 반복 = 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍

 

풀이1 - DFS 이용

let inputComputer = Int(readLine()!)!
let inputNetword = Int(readLine()!)!

var checkArr = Array(repeating: false, count: inputComputer+1)
var arr = Array(repeating: Array(repeating: false, count: inputComputer+1), count: inputComputer+1)

for _ in 0..<inputNetword {
    let line = readLine()!.split(separator: " ").map{ Int($0)!}
    
    arr[line[0]][line[1]] = true
    arr[line[1]][line[0]] = true
}

var count = 0
func dfs(_ num: Int) {
    checkArr[num] = true
    
    for i in 1..<inputComputer+1 {
        if checkArr[i] == false && arr[num][i] == true {
            dfs(i)
            count += 1
        }
    }
}

//1번컴퓨터와 연결되어 있는 네트워크를 찾는 것
dfs(1)
print(count)

일단 입력받은 네트워크 연결을 배열에 저장해주고

1번 컴퓨터부터 순서대로 연결되어 있는 컴퓨터 번호에 방문한다.

 

 

풀이2 - BFS 이용

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        self.enQueue = queue
    }
    
    func push(_ element: T) {
        enQueue.append(element)
    }
    
    func pop() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }

    func front() -> T? {
        let newQue = deQueue.reversed() + enQueue
        return newQue.first
    }   
}

let inputComputer = Int(readLine()!)!
let inputNetword = Int(readLine()!)!

var checkArr = Array(repeating: false, count: inputComputer+1)
var arr = Array(repeating: Array(repeating: false, count: inputComputer+1), count: inputComputer+1)

for _ in 0..<inputNetword {
    let line = readLine()!.split(separator: " ").map{ Int($0)!}
    
    arr[line[0]][line[1]] = true
    arr[line[1]][line[0]] = true
}

var count = 0
func bfs(_ num: Int) {
    checkArr[num] = true
     
    let q = Queue([Int]())
    q.push(num)
    
    while !q.isEmpty {
        let last = q.pop()
        
        for i in 1..<inputComputer+1 {
            if checkArr[i] == false && arr[last][i] == true {
                checkArr[i] = true
                q.push(i)
                count += 1
            }
        }
    }
}

bfs(1)
print(count)

 

결과

DFS 이용	BFS 이용

 

 

알게된 점

이 문제는 해당 노드와 연결되어있는 노드의 개수를 구하는 문제

 

DFS 와 BFS를 반복적으로 연습중이다.

처음보다는 그래도 어느정도 개념이 잡히는 듯하다. 

이제 풀이와 구현하는 정도는 가능해졌지만 어떤 방식이 더 효율적인지는 좀 더 많은 문제를 풀어봐야겠다.