[BOJ/Swift] 바이러스 2606

Baekjoon Online Judge

문제 - 단계별로 풀어보기 - DFS와 BFS - 바이러스 2606

2606번: 바이러스

---

TODO :

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다.

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

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.

1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어

2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.

하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다.

컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

 

Constraints : 

입력

 

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

출력

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

 

Sample Input :

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

 

Sample Output :

4

 

Solution.swift : 

//  DFS/바이러스_2606
//
//  Created by Yongwoo Marco on 2021/08/18.
//

import Foundation

let computerCount = Int(readLine()!)!
let networkCount = Int(readLine()!)!

var computers = [(Bool, Set<Int>)](repeating: (false, []), count: computerCount + 1)

for _ in 1...networkCount {
    let input = readLine()!.components(separatedBy: " ").map({ Int($0)! })
 
    computers[input[0]].1.update(with: input[1])
    computers[input[1]].1.update(with: input[0])
}

func spread(from: Int, network: inout [(Bool, Set<Int>)]) {
    if network[from].0 == true {
        return
    }
    network[from].0 = true
    network[from].1.forEach({ spread(from: $0, network: &network) })
}

spread(from: 1, network: &computers)

let result = computers.filter({ $0.0 == true }).count

print(result - 1)

github Code Repositoriy

 

How I tried this :

일단 각 컴퓨터가 연결된 네트워크를 인접리스트 형태로 저장시키고 

1번 컴퓨터를 출발점으로 연결된 모든 컴퓨터가 다시 출발점이 되서 확산시키는 함수를 구현해보았다.

 

생각보다 간단한 형태여서 바로 풀린거로 기대했는데...

 

테스트용 print문을 주석처리 안하고 했다가.. 한번에 기회를 날림.. ㅋㅋㅋ

시간복잡도 생각해보기

컴퓨터 수는 최대 100대 이하인데 네트워크 제한은 없다. 

만약 1-2-3처럼 한대씩 100대 컴퓨터가 연결된다면 해당 함수를 100번 호출할테고

1컴퓨터에 99대 컴퓨터가 연결되어도 100번 호출될것 같다..

O(컴퓨터대수) 일려나.. O(네트워크갯수)일려나.. 무튼 크지않다.. 간단하고 구현해내면 풀리는 문제 같다..

 

What I got is : 

 

 

I have to study :

 

문제에 관한 모든 저작권 : https://www.acmicpc.net/

Baekjoon Online Judge