[Algorithm] 2606 - 바이러스

[hwangJi-dev]

💬 문제

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

💬 Idea

• 양방향 그래프를 만든 뒤 DFS 탐색을 하여 1번 컴퓨터와 연결된 리스트를 구한다.
• 1번 컴퓨터를 제외한 감염 컴퓨터 수를 출력한다

💬 풀이

import Foundation

func solution2606() -> Int {
 let computerCount = Int(readLine()!)!
 let connectCount = Int(readLine()!)!
 
 var graph: [String: [String]] = [:]
 
 for _ in 0..<connectCount {
 let connect = readLine()!.split(whereSeparator: { $0 == " " }).map({ String($0) })
 let node1 = connect[0]
 let node2 = connect[1]
 
 if graph[node1] == nil {
 graph[node1] = [node2]
 } else {
 graph[node1]?.append(node2)
 }
 
 if graph[node2] == nil {
 graph[node2] = [node1]
 } else {
 graph[node2]?.append(node1)
 }
 }
 
 let warmVirusComputerArr = dfs(graph, "1")
 return warmVirusComputerArr.count - 1
}

func dfs(_ graph: [String: [String]], _ start: String) -> [String] {
 var needToVisitStack: [String] = [start]
 var visitedQueue: [String] = []
 
 while !needToVisitStack.isEmpty {
 let node = needToVisitStack.removeLast()
 
 if visitedQueue.contains(node) { continue }
 visitedQueue.append(node)
 
 needToVisitStack += graph[node] ?? []
 }
 
 return visitedQueue
}

소요시간 : 25분