[swift] 네트워크

📌 프로그래머스 Lv - 3

💪 오늘도 하루 최소 한 문제 해결!!

📝 KeyWord

⇢ BFS / DFS : [너비 우선 탐색, 깊이 우선탐색]
⇢ Graph

생각보다 간단하게 풀렸다. 동일한 Lv3 문제 중에서 아마 가장 쉬운 난이도로
볼 수 있다. BFS / DFS 라는 개념을 알고 있다면, 쉽게 해결할 수 있다!

📌 문제풀이

---

⇢ 제시된 Graph의 연결상태를 통해, 어떻게 네트워크를 연결할 것 인가?
⇢ 각각의 노드를 중복해서 방문하지 않도록 어떻게 처리할 것 인가?

먼저, BFS(너비우선탐색)으로 문제를 해결하기 위해 다음과 같은 변수 선언이 필요하다.
(1) 각각의 노드를 방문할 경우, "Visit" 방문 처리를 진행한다
(2) 한 노드에서 탐색이 완료될 때마다, network의 개수를 저장한다.
최종적으로, 0부터 N-1번까지의 모든 노드를 BFS로 탐색하면서 탐색을 실행 할 때마, 서로 연결되지 않은 네트워크로 간주하여 개수를 1씩 늘려간다.

위의 코드는 단순히, BFS를 구현한 코드이다. C/C++에 익숙한 탓에, 주로 전역변수보다는 포인터를 활용한 매개변수를 사용하였는데, swift로 전환하면서 inout을 많이 활용하게 되는 것 같다..

📝 전체코드

import Foundation

func BFS(_ startNode: Int,_ computers:[[Int]],_ visit: inout [Bool]){
    
    var Queue: [Int] = []
    Queue.append(startNode)
    visit[startNode] = true
    while !Queue.isEmpty{
        let Node = Queue.removeFirst()
        for  nextNode in 0..<computers.count{
            if computers[Node][nextNode] == 1 && !visit[nextNode] {
                Queue.append(nextNode)
                visit[nextNode] = true
            }
        }
    }
}

func solution(_ n:Int, _ computers:[[Int]]) -> Int {
    
    var visit:[Bool] = Array(repeating: false, count: computers.count)
    var networkCnt = 0
    for node in 0..<computers.count
    {
        if visit[node] == false
        {
            BFS(node, computers, &visit)
            networkCnt += 1
        }
    }
    return networkCnt
}