웜 바이러스_DFS

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 전형적인 그래프 탐색 문제로 DFS or BFS로 문제를 해결할 수 있음
• 인접한 노드를 방문할 때 마다, count 값을 증가시켜줌으로써 문제를 해결할 수 있고, O(N + M)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 웜 바이러스

//MARK: - Framework
import Foundation

//MARK: - Type
struct Graph {
    //MARK: - Property
    var edges: [Int]
    
    //MARK: - Initializer
    init() {
        self.edges = []
    }
}

//MARK: - Variable
var graph: [Graph] = []
var visited: [Bool] = []
var count: Int = 0

//MARK: - Function
func dfs(_ x: Int) -> Void {
    visited[x] = true
    
    for i in 0..<graph[x].edges.count {
        let y: Int = graph[x].edges[i]
        
        if !visited[y] {
            count += 1
            dfs(y)
        }
    }
}

func solution() -> Void {
    //MARK: - Input
    guard let N: Int = Int(readLine() ?? "0") else { return }
    guard let M: Int = Int(readLine() ?? "0") else { return }
    graph = Array(repeating: Graph(), count: N + 10)
    visited = Array(repeating: false, count: N + 10)
    
    for _ in 0..<M {
        guard let inputData = readLine()?.components(separatedBy: " ") else { return }
        let a: Int = inputData.map { Int($0) }[0] ?? 0
        let b: Int = inputData.map { Int($0) }[1] ?? 0
        
        graph[a].edges.append(b)
        graph[b].edges.append(a)
    }
    
    //MARK: - Process
    dfs(1)
    
    //MARK: - Output
    print(count)
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.