[Swift] BOJ 2606 바이러스

BOJ 2606 바이러스

 

✅ 이건 진짜 쉬웠음. ( solved.ac 기준 실3 )

사실 이전에 다른 문제가 안풀려서 이걸로 이동함

그 문제는 문제 설계는 했는데, 뭔가 어디서 오류가 나는지 제대로 안되어서 걍 패스했음.

 

다른건 아니고 주의할 점 하나만 남겨두겠음.

내가 흔히 하는 실수 중 하나가, 데이터를 입력 받는 순간에서 저지르는 실수인데 

그래프 형태라면 서로가 서로를 배열에 담아야 함.

무슨 말이냐면 나는 주로 [ Int: [Int] ] 형태로 입력을 처리하는데

2번과 5번의 경우

2: [1,3,5] 

5: [1,2,6]

이렇게 가져야한다는 말임.

근데 나는 트리처럼 처리를 해서 실수를 종종함.

그래프형태

나는 그냥 DFS로 했는데 BFS사용해도 상관 없음

 

🟠 코드

import Foundation

struct b2606 {
    static func run() {
        // Input 처리
        var n = Int(readLine()!)!
        var input = Int(readLine()!)!
        
        var list = [Int: [Int]]()
        
        for _ in 0..<input {
            let line = readLine()!.split(separator: " ").map{ Int(String($0))! }
            let start = line[0]
            let end = line[1]
            
            if list[start] == nil {
                list[start] = [end]
            } else {
                list[start]?.append(end)
            }
            
            if list[end] == nil {
                list[end] = [start]
            } else {
                list[end]?.append(start)
            }
        }
        
//        print(list)
        let a = DFS(graph: list, start: 1)
        print(a.count-1)
    }
}

import Foundation

func DFS<T> (graph: [T: [T]], start: T) -> [T] {
    var visitedQueue: [T] = []
    var needVisitStack: [T] = [start]
    
    while !needVisitStack.isEmpty {
        let node: T = needVisitStack.removeLast()
        if visitedQueue.contains(node) { continue }
        
        visitedQueue.append(node)
        needVisitStack += graph[node] ?? []
    }
    
    return visitedQueue
}